<!DOCTYPE html><html lang="en">
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>[2406.04520] Natural Plan: Benchmarking LLMs on Natural Language Planning</title><meta property="og:description" content="We introduce Natural Plan, a realistic planning benchmark in natural language containing 3 key tasks: Trip Planning, Meeting Planning, and Calendar Scheduling. We focus our evaluation on the planning capabilities of LL…">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Natural Plan: Benchmarking LLMs on Natural Language Planning">
<meta name="twitter:image:src" content="https://ar5iv.labs.arxiv.org/assets/ar5iv_card.png">
<meta name="twitter:image:alt" content="ar5iv logo">
<meta property="og:title" content="Natural Plan: Benchmarking LLMs on Natural Language Planning">
<meta property="og:site_name" content="ar5iv">
<meta property="og:image" content="https://ar5iv.labs.arxiv.org/assets/ar5iv_card.png">
<meta property="og:type" content="article">
<meta property="og:url" content="https://ar5iv.labs.arxiv.org/html/2406.04520">

<!--Generated on Fri Jul  5 21:12:39 2024 by LaTeXML (version 0.8.8) http://dlmf.nist.gov/LaTeXML/.-->
<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">

<script>
  function detectColorScheme(){
    var theme="light";
    var current_theme = localStorage.getItem("ar5iv_theme");
    if(current_theme){
      if(current_theme == "dark"){
        theme = "dark";
      } }
    else if(!window.matchMedia) { return false; }
    else if(window.matchMedia("(prefers-color-scheme: dark)").matches) {
      theme = "dark"; }
    if (theme=="dark") {
      document.documentElement.setAttribute("data-theme", "dark");
    } else {
      document.documentElement.setAttribute("data-theme", "light"); } }

  detectColorScheme();

  function toggleColorScheme(){
    var current_theme = localStorage.getItem("ar5iv_theme");
    if (current_theme) {
      if (current_theme == "light") {
        localStorage.setItem("ar5iv_theme", "dark"); }
      else {
        localStorage.setItem("ar5iv_theme", "light"); } }
    else {
        localStorage.setItem("ar5iv_theme", "dark"); }
    detectColorScheme(); }
</script>
<link media="all" rel="stylesheet" href="/assets/ar5iv-fonts.0.7.9.min.css"><link media="all" rel="stylesheet" href="/assets/ar5iv.0.7.9.min.css"><link media="all" rel="stylesheet" href="/assets/ar5iv-site.0.2.2.css">
</head>
<body>
<div class="ltx_page_main">
<div class="ltx_page_content">
<article class="ltx_document ltx_authors_1line">
<h1 class="ltx_title ltx_title_document">
<span id="id1.id1" class="ltx_text ltx_font_smallcaps">Natural Plan</span>: Benchmarking LLMs on Natural Language Planning</h1>
<div class="ltx_authors">
<span class="ltx_creator ltx_role_author">
<span class="ltx_personname">Huaixiu Steven Zheng  Swaroop Mishra  Hugh Zhang
<br class="ltx_break"><span id="id2.1.id1" class="ltx_text ltx_font_bold">Xinyun Chen  Minmin Chen  Azade Nova  Le Hou
<br class="ltx_break">Heng-Tze Cheng  Quoc V. Le  Ed H. Chi  Denny Zhou</span>

<br class="ltx_break">
Google DeepMind 
<br class="ltx_break">
</span><span class="ltx_author_notes">Currently at Scale AI, work done while interning at Google Deepmind</span></span>
</div>

<div class="ltx_abstract">
<h6 class="ltx_title ltx_title_abstract">Abstract</h6>
<p id="id3.id1" class="ltx_p">We introduce <span id="id3.id1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span>, a realistic planning benchmark in natural language containing 3 key tasks: <em id="id3.id1.2" class="ltx_emph ltx_font_italic">Trip Planning</em>, <em id="id3.id1.3" class="ltx_emph ltx_font_italic">Meeting Planning</em>, and <em id="id3.id1.4" class="ltx_emph ltx_font_italic">Calendar Scheduling</em>. We focus our evaluation on the planning capabilities of LLMs with full information on the task, by providing outputs from tools such as Google Flights, Google Maps, and Google Calendar as contexts to the models. This eliminates the need for a tool-use environment for evaluating LLMs on Planning. We observe that <span id="id3.id1.5" class="ltx_text ltx_font_smallcaps">Natural Plan</span> is a challenging benchmark for state of the art models. For example, in <span id="id3.id1.6" class="ltx_text ltx_font_italic">Trip Planning</span>, GPT-4 and Gemini 1.5 Pro could only achieve 31.1% and 34.8% solve rate respectively. We find that model performance drops drastically as the complexity of the problem increases: all models perform below 5% when there are 10 cities, highlighting a significant gap in planning in natural language for SoTA LLMs. We also conduct extensive ablation studies on <span id="id3.id1.7" class="ltx_text ltx_font_smallcaps">Natural Plan</span> to further shed light on the (in)effectiveness of approaches such as self-correction, few-shot generalization, and in-context planning with long-contexts on improving LLM planning.</p>
</div>
<section id="S1" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">1 </span>Introduction</h2>

<div id="S1.p1" class="ltx_para ltx_noindent">
<p id="S1.p1.1" class="ltx_p">Large language models (LLMs) such as Gemini <cite class="ltx_cite ltx_citemacro_citep">(Team et al., <a href="#bib.bib27" title="" class="ltx_ref">2023</a>)</cite> and GPT4 <cite class="ltx_cite ltx_citemacro_citep">(Achiam et al., <a href="#bib.bib1" title="" class="ltx_ref">2023</a>)</cite> have demonstrated great potentials in solving complex tasks, such as understanding natural language <cite class="ltx_cite ltx_citemacro_citep">(Winograd, <a href="#bib.bib31" title="" class="ltx_ref">1972</a>)</cite>, reasoning <cite class="ltx_cite ltx_citemacro_citep">(Cobbe et al., <a href="#bib.bib6" title="" class="ltx_ref">2021</a>)</cite> and code generation <cite class="ltx_cite ltx_citemacro_citep">(Chen et al., <a href="#bib.bib5" title="" class="ltx_ref">2021</a>)</cite>. The planning capability of these models however are still far behind human performance <cite class="ltx_cite ltx_citemacro_citep">(Xie et al., <a href="#bib.bib32" title="" class="ltx_ref">2024</a>)</cite>. Even though many recent works target to tackle this problem, without realistic benchmarks that reflect real-world applications, it is difficult to make meaningful progress in enhancing these models’ planning abilities.</p>
</div>
<div id="S1.p2" class="ltx_para ltx_noindent">
<p id="S1.p2.1" class="ltx_p">Planning <cite class="ltx_cite ltx_citemacro_citep">(Russell and Norvig, <a href="#bib.bib24" title="" class="ltx_ref">2016</a>)</cite> has been exhaustively studied in robotics and embodied environments <cite class="ltx_cite ltx_citemacro_citep">(LaValle, <a href="#bib.bib20" title="" class="ltx_ref">2006</a>; Camacho et al., <a href="#bib.bib4" title="" class="ltx_ref">2007</a>; Jiang et al., <a href="#bib.bib17" title="" class="ltx_ref">2019a</a>)</cite>. Automated planning algorithms
have been widely used  <cite class="ltx_cite ltx_citemacro_citep">(Zhang et al., <a href="#bib.bib34" title="" class="ltx_ref">2015</a>; Lagriffoul et al., <a href="#bib.bib19" title="" class="ltx_ref">2018</a>; Jiang et al., <a href="#bib.bib18" title="" class="ltx_ref">2019b</a>; Ding et al., <a href="#bib.bib7" title="" class="ltx_ref">2020</a>)</cite> to enable planning in such systems. In these settings, planning involves coming up with a sequence of actions which when executed would take an agent from a certain initial state to a desired world state. These systems frequently use planning domain description language (PDDL) <cite class="ltx_cite ltx_citemacro_citep">(McDermott et al., <a href="#bib.bib23" title="" class="ltx_ref">1998</a>)</cite> or answer set programming (ASP) <cite class="ltx_cite ltx_citemacro_citep">(Brewka et al., <a href="#bib.bib2" title="" class="ltx_ref">2011</a>)</cite> as the underlying action language for the planners. Even though recent works have explored the potential of LLM-powered agents in classical planning settings <cite class="ltx_cite ltx_citemacro_citep">(Silver et al., <a href="#bib.bib25" title="" class="ltx_ref">2023</a>; Liu et al., <a href="#bib.bib21" title="" class="ltx_ref">2023</a>; Hao et al., <a href="#bib.bib12" title="" class="ltx_ref">2023</a>; Valmeekam et al., <a href="#bib.bib29" title="" class="ltx_ref">2024</a>; Wang et al., <a href="#bib.bib30" title="" class="ltx_ref">2023</a>; Guan et al., <a href="#bib.bib11" title="" class="ltx_ref">2024</a>)</cite>, planning scenarios are not in practical setting and they are not in natural language as they often contains templates.</p>
</div>
<figure id="S1.F1" class="ltx_figure"><img src="/html/2406.04520/assets/Teaser1aa.png" id="S1.F1.1.g1" class="ltx_graphics ltx_centering ltx_img_landscape" width="598" height="155" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">Figure 1: </span>Illustrative example of the <em id="S1.F1.3.1" class="ltx_emph ltx_font_italic">Trip Planning</em> task.</figcaption>
</figure>
<figure id="S1.F2" class="ltx_figure"><img src="/html/2406.04520/assets/Teaser1bn2.png" id="S1.F2.1.g1" class="ltx_graphics ltx_centering ltx_img_landscape" width="598" height="164" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">Figure 2: </span>Illustrative example of the <em id="S1.F2.3.1" class="ltx_emph ltx_font_italic">Meeting Planning</em> task.</figcaption>
</figure>
<figure id="S1.F3" class="ltx_figure"><img src="/html/2406.04520/assets/Teaser1cn.png" id="S1.F3.1.g1" class="ltx_graphics ltx_centering ltx_img_landscape" width="598" height="162" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">Figure 3: </span>Illustrative example of the <em id="S1.F3.3.1" class="ltx_emph ltx_font_italic">Calendar Scheduling</em> task.</figcaption>
</figure>
<div id="S1.p3" class="ltx_para ltx_noindent">
<p id="S1.p3.1" class="ltx_p">In this paper we introduce <span id="S1.p3.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span>, a new benchmark specifically designed to assess how well LLMs can handle planning tasks described in natural language. <span id="S1.p3.1.2" class="ltx_text ltx_font_smallcaps">Natural Plan</span> includes three different planning tasks i.e., <em id="S1.p3.1.3" class="ltx_emph ltx_font_italic">Trip Planning</em>, <em id="S1.p3.1.4" class="ltx_emph ltx_font_italic">Meeting Planning</em>, <em id="S1.p3.1.5" class="ltx_emph ltx_font_italic">Calendar Scheduling</em>. For each task we gather real information from the existing tools. For example, in <span id="S1.p3.1.6" class="ltx_text ltx_font_italic">Trip Planning</span> we query Google Flights API and provide the flight connectivity information between cities in the context. Figures <a href="#S1.F1" title="Figure 1 ‣ 1 Introduction ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">1</span></a>- <a href="#S1.F3" title="Figure 3 ‣ 1 Introduction ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3</span></a> illustrate the tasks along with associated google tools that provide information as context.</p>
</div>
<div id="S1.p4" class="ltx_para ltx_noindent">
<p id="S1.p4.2" class="ltx_p">Our evaluation shows that <span id="S1.p4.2.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span> is a hard benchmark for state of the art models. For example, in the <em id="S1.p4.2.2" class="ltx_emph ltx_font_italic">Trip Planning task</em>, GPT-4 and Gemini 1.5 Pro achieves 31.1% and 34.8% performance, while GPT-3.5 is only at 7.3% and GPT-4o is at 3.7%. We find that model performance reduces significantly as the complexity of the task increases e.g. an increase in number of people, cities or days in the question. Self-correction does not help models in improving performance. We also observe interesting insights in our easy to hard and hard to easy generalization experiments. Lastly, we conduct study of in-context planning with long context, and show that Gemini 1.5 Pro significantly outperforms other models with <math id="S1.p4.1.m1.1" class="ltx_Math" alttext="\sim 40\%" display="inline"><semantics id="S1.p4.1.m1.1a"><mrow id="S1.p4.1.m1.1.1" xref="S1.p4.1.m1.1.1.cmml"><mi id="S1.p4.1.m1.1.1.2" xref="S1.p4.1.m1.1.1.2.cmml"></mi><mo id="S1.p4.1.m1.1.1.1" xref="S1.p4.1.m1.1.1.1.cmml">∼</mo><mrow id="S1.p4.1.m1.1.1.3" xref="S1.p4.1.m1.1.1.3.cmml"><mn id="S1.p4.1.m1.1.1.3.2" xref="S1.p4.1.m1.1.1.3.2.cmml">40</mn><mo id="S1.p4.1.m1.1.1.3.1" xref="S1.p4.1.m1.1.1.3.1.cmml">%</mo></mrow></mrow><annotation-xml encoding="MathML-Content" id="S1.p4.1.m1.1b"><apply id="S1.p4.1.m1.1.1.cmml" xref="S1.p4.1.m1.1.1"><csymbol cd="latexml" id="S1.p4.1.m1.1.1.1.cmml" xref="S1.p4.1.m1.1.1.1">similar-to</csymbol><csymbol cd="latexml" id="S1.p4.1.m1.1.1.2.cmml" xref="S1.p4.1.m1.1.1.2">absent</csymbol><apply id="S1.p4.1.m1.1.1.3.cmml" xref="S1.p4.1.m1.1.1.3"><csymbol cd="latexml" id="S1.p4.1.m1.1.1.3.1.cmml" xref="S1.p4.1.m1.1.1.3.1">percent</csymbol><cn type="integer" id="S1.p4.1.m1.1.1.3.2.cmml" xref="S1.p4.1.m1.1.1.3.2">40</cn></apply></apply></annotation-xml><annotation encoding="application/x-tex" id="S1.p4.1.m1.1c">\sim 40\%</annotation></semantics></math> accuracy on Trip Planning and <math id="S1.p4.2.m2.1" class="ltx_Math" alttext="\sim 50\%" display="inline"><semantics id="S1.p4.2.m2.1a"><mrow id="S1.p4.2.m2.1.1" xref="S1.p4.2.m2.1.1.cmml"><mi id="S1.p4.2.m2.1.1.2" xref="S1.p4.2.m2.1.1.2.cmml"></mi><mo id="S1.p4.2.m2.1.1.1" xref="S1.p4.2.m2.1.1.1.cmml">∼</mo><mrow id="S1.p4.2.m2.1.1.3" xref="S1.p4.2.m2.1.1.3.cmml"><mn id="S1.p4.2.m2.1.1.3.2" xref="S1.p4.2.m2.1.1.3.2.cmml">50</mn><mo id="S1.p4.2.m2.1.1.3.1" xref="S1.p4.2.m2.1.1.3.1.cmml">%</mo></mrow></mrow><annotation-xml encoding="MathML-Content" id="S1.p4.2.m2.1b"><apply id="S1.p4.2.m2.1.1.cmml" xref="S1.p4.2.m2.1.1"><csymbol cd="latexml" id="S1.p4.2.m2.1.1.1.cmml" xref="S1.p4.2.m2.1.1.1">similar-to</csymbol><csymbol cd="latexml" id="S1.p4.2.m2.1.1.2.cmml" xref="S1.p4.2.m2.1.1.2">absent</csymbol><apply id="S1.p4.2.m2.1.1.3.cmml" xref="S1.p4.2.m2.1.1.3"><csymbol cd="latexml" id="S1.p4.2.m2.1.1.3.1.cmml" xref="S1.p4.2.m2.1.1.3.1">percent</csymbol><cn type="integer" id="S1.p4.2.m2.1.1.3.2.cmml" xref="S1.p4.2.m2.1.1.3.2">50</cn></apply></apply></annotation-xml><annotation encoding="application/x-tex" id="S1.p4.2.m2.1c">\sim 50\%</annotation></semantics></math> on Calendar Scheduling.</p>
</div>
</section>
<section id="S2" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">2 </span><span id="S2.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span>
</h2>

<div id="S2.p1" class="ltx_para ltx_noindent">
<p id="S2.p1.1" class="ltx_p"><span id="S2.p1.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span> is a benchmark designed to evaluate capability of LLMs in performing planning tasks expressed in natural language. In this section, we discuss about various categories we have in <span id="S2.p1.1.2" class="ltx_text ltx_font_smallcaps">Natural Plan</span>, our dataset construction process, quality measures and some statistics.</p>
</div>
<section id="S2.SS1" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">2.1 </span>Dataset Categories</h3>

<div id="S2.SS1.p1" class="ltx_para ltx_noindent">
<p id="S2.SS1.p1.1" class="ltx_p"><span id="S2.SS1.p1.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span> has 3 planning categories: <em id="S2.SS1.p1.1.2" class="ltx_emph ltx_font_italic">Trip Planning</em>, <em id="S2.SS1.p1.1.3" class="ltx_emph ltx_font_italic">Meeting Planning</em> and <em id="S2.SS1.p1.1.4" class="ltx_emph ltx_font_italic">Calendar Scheduling</em>. Each of these is intended to capture a real world planning task involving some tools such as Google flights. We decouple tool-use from the reasoning task and provide tool outputs in-context to keep focus of <span id="S2.SS1.p1.1.5" class="ltx_text ltx_font_smallcaps">Natural Plan</span> on planning. We believe this will significantly simplify the process of evaluating planning for LLMs.</p>
</div>
<section id="S2.SS1.SSS1" class="ltx_subsubsection">
<h4 class="ltx_title ltx_title_subsubsection">
<span class="ltx_tag ltx_tag_subsubsection">2.1.1 </span><em id="S2.SS1.SSS1.1.1" class="ltx_emph ltx_font_italic">Trip Planning</em>
</h4>

<div id="S2.SS1.SSS1.p1" class="ltx_para ltx_noindent">
<p id="S2.SS1.SSS1.p1.1" class="ltx_p"><em id="S2.SS1.SSS1.p1.1.1" class="ltx_emph ltx_font_italic">Trip Planning</em> is a task focusing on planning a trip itinerary under given constraints. An example prompt and solution is shown in Appendix <a href="#A1" title="Appendix A Natural Plan Examples ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">A</span></a>. The task is to find the itinerary regarding the order of visiting <math id="S2.SS1.SSS1.p1.1.m1.1" class="ltx_Math" alttext="N" display="inline"><semantics id="S2.SS1.SSS1.p1.1.m1.1a"><mi id="S2.SS1.SSS1.p1.1.m1.1.1" xref="S2.SS1.SSS1.p1.1.m1.1.1.cmml">N</mi><annotation-xml encoding="MathML-Content" id="S2.SS1.SSS1.p1.1.m1.1b"><ci id="S2.SS1.SSS1.p1.1.m1.1.1.cmml" xref="S2.SS1.SSS1.p1.1.m1.1.1">𝑁</ci></annotation-xml><annotation encoding="application/x-tex" id="S2.SS1.SSS1.p1.1.m1.1c">N</annotation></semantics></math> cities. We add enough constraints such that there is only one solution to the task, which makes the evaluation of the predictions straightforward.</p>
</div>
</section>
<section id="S2.SS1.SSS2" class="ltx_subsubsection">
<h4 class="ltx_title ltx_title_subsubsection">
<span class="ltx_tag ltx_tag_subsubsection">2.1.2 </span><em id="S2.SS1.SSS2.1.1" class="ltx_emph ltx_font_italic">Meeting Planning</em>
</h4>

<div id="S2.SS1.SSS2.p1" class="ltx_para ltx_noindent">
<p id="S2.SS1.SSS2.p1.1" class="ltx_p">This portion of the benchmark focuses on scheduling meetings under various given constraints. Given <math id="S2.SS1.SSS2.p1.1.m1.1" class="ltx_Math" alttext="N" display="inline"><semantics id="S2.SS1.SSS2.p1.1.m1.1a"><mi id="S2.SS1.SSS2.p1.1.m1.1.1" xref="S2.SS1.SSS2.p1.1.m1.1.1.cmml">N</mi><annotation-xml encoding="MathML-Content" id="S2.SS1.SSS2.p1.1.m1.1b"><ci id="S2.SS1.SSS2.p1.1.m1.1.1.cmml" xref="S2.SS1.SSS2.p1.1.m1.1.1">𝑁</ci></annotation-xml><annotation encoding="application/x-tex" id="S2.SS1.SSS2.p1.1.m1.1c">N</annotation></semantics></math> friends, this task provides the meeting times as well as their locations. Appendix <a href="#A1" title="Appendix A Natural Plan Examples ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">A</span></a> demonstrates an example question. The objective is to meet as many friends as possible given the constraints, which include travel time between locations.</p>
</div>
</section>
<section id="S2.SS1.SSS3" class="ltx_subsubsection">
<h4 class="ltx_title ltx_title_subsubsection">
<span class="ltx_tag ltx_tag_subsubsection">2.1.3 </span><em id="S2.SS1.SSS3.1.1" class="ltx_emph ltx_font_italic">Calendar Scheduling</em>
</h4>

<div id="S2.SS1.SSS3.p1" class="ltx_para ltx_noindent">
<p id="S2.SS1.SSS3.p1.1" class="ltx_p"><em id="S2.SS1.SSS3.p1.1.1" class="ltx_emph ltx_font_italic">Calendar Scheduling</em> is a task focusing on scheduling work meetings between multiple people given existing schedules and various constraints. We vary the number of people involved in the meeting and the number of workdays, in order to vary the task difficulties. Appendix <a href="#A1" title="Appendix A Natural Plan Examples ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">A</span></a> demonstrates an example question.</p>
</div>
</section>
</section>
<section id="S2.SS2" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">2.2 </span>Dataset Construction</h3>

<div id="S2.SS2.p1" class="ltx_para ltx_noindent">
<p id="S2.SS2.p1.1" class="ltx_p">We create <span id="S2.SS2.p1.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span> synthetically by using corresponding tool data and creating various constraints. We describe below the specific creation process for each category of task.</p>
</div>
<section id="S2.SS2.SSS1" class="ltx_subsubsection">
<h4 class="ltx_title ltx_title_subsubsection">
<span class="ltx_tag ltx_tag_subsubsection">2.2.1 </span><span id="S2.SS2.SSS1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span>
</h4>

<div id="S2.SS2.SSS1.p1" class="ltx_para ltx_noindent">
<p id="S2.SS2.SSS1.p1.2" class="ltx_p">We create the dataset in the following way: To create a question, we randomly sample <math id="S2.SS2.SSS1.p1.1.m1.2" class="ltx_Math" alttext="N\in[3,10]" display="inline"><semantics id="S2.SS2.SSS1.p1.1.m1.2a"><mrow id="S2.SS2.SSS1.p1.1.m1.2.3" xref="S2.SS2.SSS1.p1.1.m1.2.3.cmml"><mi id="S2.SS2.SSS1.p1.1.m1.2.3.2" xref="S2.SS2.SSS1.p1.1.m1.2.3.2.cmml">N</mi><mo id="S2.SS2.SSS1.p1.1.m1.2.3.1" xref="S2.SS2.SSS1.p1.1.m1.2.3.1.cmml">∈</mo><mrow id="S2.SS2.SSS1.p1.1.m1.2.3.3.2" xref="S2.SS2.SSS1.p1.1.m1.2.3.3.1.cmml"><mo stretchy="false" id="S2.SS2.SSS1.p1.1.m1.2.3.3.2.1" xref="S2.SS2.SSS1.p1.1.m1.2.3.3.1.cmml">[</mo><mn id="S2.SS2.SSS1.p1.1.m1.1.1" xref="S2.SS2.SSS1.p1.1.m1.1.1.cmml">3</mn><mo id="S2.SS2.SSS1.p1.1.m1.2.3.3.2.2" xref="S2.SS2.SSS1.p1.1.m1.2.3.3.1.cmml">,</mo><mn id="S2.SS2.SSS1.p1.1.m1.2.2" xref="S2.SS2.SSS1.p1.1.m1.2.2.cmml">10</mn><mo stretchy="false" id="S2.SS2.SSS1.p1.1.m1.2.3.3.2.3" xref="S2.SS2.SSS1.p1.1.m1.2.3.3.1.cmml">]</mo></mrow></mrow><annotation-xml encoding="MathML-Content" id="S2.SS2.SSS1.p1.1.m1.2b"><apply id="S2.SS2.SSS1.p1.1.m1.2.3.cmml" xref="S2.SS2.SSS1.p1.1.m1.2.3"><in id="S2.SS2.SSS1.p1.1.m1.2.3.1.cmml" xref="S2.SS2.SSS1.p1.1.m1.2.3.1"></in><ci id="S2.SS2.SSS1.p1.1.m1.2.3.2.cmml" xref="S2.SS2.SSS1.p1.1.m1.2.3.2">𝑁</ci><interval closure="closed" id="S2.SS2.SSS1.p1.1.m1.2.3.3.1.cmml" xref="S2.SS2.SSS1.p1.1.m1.2.3.3.2"><cn type="integer" id="S2.SS2.SSS1.p1.1.m1.1.1.cmml" xref="S2.SS2.SSS1.p1.1.m1.1.1">3</cn><cn type="integer" id="S2.SS2.SSS1.p1.1.m1.2.2.cmml" xref="S2.SS2.SSS1.p1.1.m1.2.2">10</cn></interval></apply></annotation-xml><annotation encoding="application/x-tex" id="S2.SS2.SSS1.p1.1.m1.2c">N\in[3,10]</annotation></semantics></math> cities from the top-48 visited cities in Europe. We also randomly sample the total duration and the number of days spent in each city with <math id="S2.SS2.SSS1.p1.2.m2.2" class="ltx_Math" alttext="D\in[2,7]" display="inline"><semantics id="S2.SS2.SSS1.p1.2.m2.2a"><mrow id="S2.SS2.SSS1.p1.2.m2.2.3" xref="S2.SS2.SSS1.p1.2.m2.2.3.cmml"><mi id="S2.SS2.SSS1.p1.2.m2.2.3.2" xref="S2.SS2.SSS1.p1.2.m2.2.3.2.cmml">D</mi><mo id="S2.SS2.SSS1.p1.2.m2.2.3.1" xref="S2.SS2.SSS1.p1.2.m2.2.3.1.cmml">∈</mo><mrow id="S2.SS2.SSS1.p1.2.m2.2.3.3.2" xref="S2.SS2.SSS1.p1.2.m2.2.3.3.1.cmml"><mo stretchy="false" id="S2.SS2.SSS1.p1.2.m2.2.3.3.2.1" xref="S2.SS2.SSS1.p1.2.m2.2.3.3.1.cmml">[</mo><mn id="S2.SS2.SSS1.p1.2.m2.1.1" xref="S2.SS2.SSS1.p1.2.m2.1.1.cmml">2</mn><mo id="S2.SS2.SSS1.p1.2.m2.2.3.3.2.2" xref="S2.SS2.SSS1.p1.2.m2.2.3.3.1.cmml">,</mo><mn id="S2.SS2.SSS1.p1.2.m2.2.2" xref="S2.SS2.SSS1.p1.2.m2.2.2.cmml">7</mn><mo stretchy="false" id="S2.SS2.SSS1.p1.2.m2.2.3.3.2.3" xref="S2.SS2.SSS1.p1.2.m2.2.3.3.1.cmml">]</mo></mrow></mrow><annotation-xml encoding="MathML-Content" id="S2.SS2.SSS1.p1.2.m2.2b"><apply id="S2.SS2.SSS1.p1.2.m2.2.3.cmml" xref="S2.SS2.SSS1.p1.2.m2.2.3"><in id="S2.SS2.SSS1.p1.2.m2.2.3.1.cmml" xref="S2.SS2.SSS1.p1.2.m2.2.3.1"></in><ci id="S2.SS2.SSS1.p1.2.m2.2.3.2.cmml" xref="S2.SS2.SSS1.p1.2.m2.2.3.2">𝐷</ci><interval closure="closed" id="S2.SS2.SSS1.p1.2.m2.2.3.3.1.cmml" xref="S2.SS2.SSS1.p1.2.m2.2.3.3.2"><cn type="integer" id="S2.SS2.SSS1.p1.2.m2.1.1.cmml" xref="S2.SS2.SSS1.p1.2.m2.1.1">2</cn><cn type="integer" id="S2.SS2.SSS1.p1.2.m2.2.2.cmml" xref="S2.SS2.SSS1.p1.2.m2.2.2">7</cn></interval></apply></annotation-xml><annotation encoding="application/x-tex" id="S2.SS2.SSS1.p1.2.m2.2c">D\in[2,7]</annotation></semantics></math>. We add constraints to the itinerary requiring visiting some cities during particular days, e.g. <span id="S2.SS2.SSS1.p1.2.1" class="ltx_text ltx_font_italic">meeting a friend in Paris from day 3 to day 5 on the trip</span>. As a global constraint, we add the preference of commuting between cities using direct flights only, excluding the possibility of visiting city Y after X if there is no direct flight from X to Y. To assist the LLM with the connectivity constraint, we query Google Flights API and provide the flight connectivity information between cities in the context.</p>
</div>
</section>
<section id="S2.SS2.SSS2" class="ltx_subsubsection">
<h4 class="ltx_title ltx_title_subsubsection">
<span class="ltx_tag ltx_tag_subsubsection">2.2.2 </span><span id="S2.SS2.SSS2.1.1" class="ltx_text ltx_font_italic">Meeting Planning</span>
</h4>

<div id="S2.SS2.SSS2.p1" class="ltx_para ltx_noindent">
<p id="S2.SS2.SSS2.p1.1" class="ltx_p">For this dataset category, we randomly sample the person names to meet with and corresponding locations. We also sample time frames showing availability of persons. We add constraints in terms of availability of the subject e.g. you are visiting San Francisco for a day. The goal in this set up is to meet as many friends as possible. In order to make the problem realistic, the time constraints / locations follow real world locations. Travel distances are estimated by querying driving times via the Google Maps API.</p>
</div>
</section>
<section id="S2.SS2.SSS3" class="ltx_subsubsection">
<h4 class="ltx_title ltx_title_subsubsection">
<span class="ltx_tag ltx_tag_subsubsection">2.2.3 </span><span id="S2.SS2.SSS3.1.1" class="ltx_text ltx_font_italic">Calendar Scheduling</span>
</h4>

<div id="S2.SS2.SSS3.p1" class="ltx_para ltx_noindent">
<p id="S2.SS2.SSS3.p1.4" class="ltx_p">This portion of the dataset includes tasks to schedule a meeting of either 30 minutes or an hour among various number of attendees in one or multiple of the work days.
We instantiated two subsets: the first set fixes the meeting on a specific day, e.g., Monday while varying the number of attendees in <math id="S2.SS2.SSS3.p1.1.m1.2" class="ltx_Math" alttext="[2,7]" display="inline"><semantics id="S2.SS2.SSS3.p1.1.m1.2a"><mrow id="S2.SS2.SSS3.p1.1.m1.2.3.2" xref="S2.SS2.SSS3.p1.1.m1.2.3.1.cmml"><mo stretchy="false" id="S2.SS2.SSS3.p1.1.m1.2.3.2.1" xref="S2.SS2.SSS3.p1.1.m1.2.3.1.cmml">[</mo><mn id="S2.SS2.SSS3.p1.1.m1.1.1" xref="S2.SS2.SSS3.p1.1.m1.1.1.cmml">2</mn><mo id="S2.SS2.SSS3.p1.1.m1.2.3.2.2" xref="S2.SS2.SSS3.p1.1.m1.2.3.1.cmml">,</mo><mn id="S2.SS2.SSS3.p1.1.m1.2.2" xref="S2.SS2.SSS3.p1.1.m1.2.2.cmml">7</mn><mo stretchy="false" id="S2.SS2.SSS3.p1.1.m1.2.3.2.3" xref="S2.SS2.SSS3.p1.1.m1.2.3.1.cmml">]</mo></mrow><annotation-xml encoding="MathML-Content" id="S2.SS2.SSS3.p1.1.m1.2b"><interval closure="closed" id="S2.SS2.SSS3.p1.1.m1.2.3.1.cmml" xref="S2.SS2.SSS3.p1.1.m1.2.3.2"><cn type="integer" id="S2.SS2.SSS3.p1.1.m1.1.1.cmml" xref="S2.SS2.SSS3.p1.1.m1.1.1">2</cn><cn type="integer" id="S2.SS2.SSS3.p1.1.m1.2.2.cmml" xref="S2.SS2.SSS3.p1.1.m1.2.2">7</cn></interval></annotation-xml><annotation encoding="application/x-tex" id="S2.SS2.SSS3.p1.1.m1.2c">[2,7]</annotation></semantics></math>; the second set fixes the number of attendees to 2 while varying the number of work days the meeting can be scheduled over in <math id="S2.SS2.SSS3.p1.2.m2.2" class="ltx_Math" alttext="[1,5]" display="inline"><semantics id="S2.SS2.SSS3.p1.2.m2.2a"><mrow id="S2.SS2.SSS3.p1.2.m2.2.3.2" xref="S2.SS2.SSS3.p1.2.m2.2.3.1.cmml"><mo stretchy="false" id="S2.SS2.SSS3.p1.2.m2.2.3.2.1" xref="S2.SS2.SSS3.p1.2.m2.2.3.1.cmml">[</mo><mn id="S2.SS2.SSS3.p1.2.m2.1.1" xref="S2.SS2.SSS3.p1.2.m2.1.1.cmml">1</mn><mo id="S2.SS2.SSS3.p1.2.m2.2.3.2.2" xref="S2.SS2.SSS3.p1.2.m2.2.3.1.cmml">,</mo><mn id="S2.SS2.SSS3.p1.2.m2.2.2" xref="S2.SS2.SSS3.p1.2.m2.2.2.cmml">5</mn><mo stretchy="false" id="S2.SS2.SSS3.p1.2.m2.2.3.2.3" xref="S2.SS2.SSS3.p1.2.m2.2.3.1.cmml">]</mo></mrow><annotation-xml encoding="MathML-Content" id="S2.SS2.SSS3.p1.2.m2.2b"><interval closure="closed" id="S2.SS2.SSS3.p1.2.m2.2.3.1.cmml" xref="S2.SS2.SSS3.p1.2.m2.2.3.2"><cn type="integer" id="S2.SS2.SSS3.p1.2.m2.1.1.cmml" xref="S2.SS2.SSS3.p1.2.m2.1.1">1</cn><cn type="integer" id="S2.SS2.SSS3.p1.2.m2.2.2.cmml" xref="S2.SS2.SSS3.p1.2.m2.2.2">5</cn></interval></annotation-xml><annotation encoding="application/x-tex" id="S2.SS2.SSS3.p1.2.m2.2c">[1,5]</annotation></semantics></math>. Each person involved in the meeting comes with their existing meeting schedule during the day (first set) or the week (second set), which was created by adding random meetings of 30 minutes to the days until <math id="S2.SS2.SSS3.p1.3.m3.1" class="ltx_Math" alttext="n" display="inline"><semantics id="S2.SS2.SSS3.p1.3.m3.1a"><mi id="S2.SS2.SSS3.p1.3.m3.1.1" xref="S2.SS2.SSS3.p1.3.m3.1.1.cmml">n</mi><annotation-xml encoding="MathML-Content" id="S2.SS2.SSS3.p1.3.m3.1b"><ci id="S2.SS2.SSS3.p1.3.m3.1.1.cmml" xref="S2.SS2.SSS3.p1.3.m3.1.1">𝑛</ci></annotation-xml><annotation encoding="application/x-tex" id="S2.SS2.SSS3.p1.3.m3.1c">n</annotation></semantics></math> hours of meeting time is filled. We randomly assign <math id="S2.SS2.SSS3.p1.4.m4.1" class="ltx_Math" alttext="n" display="inline"><semantics id="S2.SS2.SSS3.p1.4.m4.1a"><mi id="S2.SS2.SSS3.p1.4.m4.1.1" xref="S2.SS2.SSS3.p1.4.m4.1.1.cmml">n</mi><annotation-xml encoding="MathML-Content" id="S2.SS2.SSS3.p1.4.m4.1b"><ci id="S2.SS2.SSS3.p1.4.m4.1.1.cmml" xref="S2.SS2.SSS3.p1.4.m4.1.1">𝑛</ci></annotation-xml><annotation encoding="application/x-tex" id="S2.SS2.SSS3.p1.4.m4.1c">n</annotation></semantics></math> to each attendee to make sure half of the attendees have busy schedule, meaning more than half of their working hours are spent in meetings, while the other half have light schedule with less than half of the working hours spent in meetings. Consecutive meetings of each attendee are combined into a single block as shown in Figure <a href="#S1.F3" title="Figure 3 ‣ 1 Introduction ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3</span></a>. Once we have the existing schedules of all attendees, we add two types of constraints: 1) earliest availability; 2) avoid meeting during certain time frame to make sure there is a single solution to the problem.</p>
</div>
</section>
</section>
<section id="S2.SS3" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">2.3 </span>Statistics</h3>

<div id="S2.SS3.p1" class="ltx_para ltx_noindent">
<p id="S2.SS3.p1.1" class="ltx_p">Table  <a href="#S2.T1" title="Table 1 ‣ 2.3 Statistics ‣ 2 Natural Plan ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">1</span></a> shows statistics of various tasks across <em id="S2.SS3.p1.1.1" class="ltx_emph ltx_font_italic">Trip Planning</em>, <em id="S2.SS3.p1.1.2" class="ltx_emph ltx_font_italic">Meeting Planning</em>, and <em id="S2.SS3.p1.1.3" class="ltx_emph ltx_font_italic">Calendar Scheduling</em> in <span id="S2.SS3.p1.1.4" class="ltx_text ltx_font_smallcaps">Natural Plan</span>.</p>
</div>
<figure id="S2.T1" class="ltx_table">
<figcaption class="ltx_caption"><span class="ltx_tag ltx_tag_table">Table 1: </span>Statistics of <span id="S2.T1.2.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span> tasks.</figcaption>
<table id="S2.T1.3" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="S2.T1.3.1" class="ltx_tr">
<td id="S2.T1.3.1.1" class="ltx_td ltx_align_center ltx_border_r ltx_border_tt">Task</td>
<td id="S2.T1.3.1.2" class="ltx_td ltx_align_center ltx_border_tt">#Test Examples</td>
</tr>
<tr id="S2.T1.3.2" class="ltx_tr">
<td id="S2.T1.3.2.1" class="ltx_td ltx_align_center ltx_border_r ltx_border_t"><span id="S2.T1.3.2.1.1" class="ltx_text ltx_font_italic">Trip Planning</span></td>
<td id="S2.T1.3.2.2" class="ltx_td ltx_align_center ltx_border_t">1600</td>
</tr>
<tr id="S2.T1.3.3" class="ltx_tr">
<td id="S2.T1.3.3.1" class="ltx_td ltx_align_center ltx_border_r ltx_border_t"><span id="S2.T1.3.3.1.1" class="ltx_text ltx_font_italic">Meeting Planning</span></td>
<td id="S2.T1.3.3.2" class="ltx_td ltx_align_center ltx_border_t">1000</td>
</tr>
<tr id="S2.T1.3.4" class="ltx_tr">
<td id="S2.T1.3.4.1" class="ltx_td ltx_align_center ltx_border_bb ltx_border_r ltx_border_t"><span id="S2.T1.3.4.1.1" class="ltx_text ltx_font_italic">Calendar Scheduling</span></td>
<td id="S2.T1.3.4.2" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">1000</td>
</tr>
</table>
</figure>
</section>
</section>
<section id="S3" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">3 </span>Experiment</h2>

<div id="S3.p1" class="ltx_para ltx_noindent">
<p id="S3.p1.1" class="ltx_p">We conduct various experiments to evaluate state-of-the-art LLMs on the planning tasks in <span id="S3.p1.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span>.</p>
</div>
<section id="S3.SS1" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">3.1 </span>Models</h3>

<div id="S3.SS1.p1" class="ltx_para ltx_noindent">
<p id="S3.SS1.p1.1" class="ltx_p">We experiment several state-of-the-art LLMs: GPT-4 (gpt-4-turbo-2024-04-09) <cite class="ltx_cite ltx_citemacro_citep">(Achiam et al., <a href="#bib.bib1" title="" class="ltx_ref">2023</a>)</cite>, GPT-3.5 (gpt-3.5-turbo-0125), GPT-4o (gpt-4o-2024-05-13), and Gemini 1.5 Flash and Pro <cite class="ltx_cite ltx_citemacro_citep">(Gemini Team, <a href="#bib.bib9" title="" class="ltx_ref">2024</a>)</cite>.</p>
</div>
</section>
<section id="S3.SS2" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">3.2 </span>Setups</h3>

<div id="S3.SS2.p1" class="ltx_para ltx_noindent">
<p id="S3.SS2.p1.1" class="ltx_p"><span id="S3.SS2.p1.1.1" class="ltx_text ltx_font_bold">Few-Shot
<br class="ltx_break"></span>For each task in <span id="S3.SS2.p1.1.2" class="ltx_text ltx_font_smallcaps">Natural Plan</span>, we present 5 examples within the same task as few-shot exemplars to enable the LLM in-context learning <cite class="ltx_cite ltx_citemacro_citep">(Brown et al., <a href="#bib.bib3" title="" class="ltx_ref">2020</a>)</cite> from the examples (see Appendix <a href="#A2" title="Appendix B Prompts ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">B</span></a> for the few-shot prompt). This setup also ensures that outputs can be easily parsed for scoring.</p>
</div>
<div id="S3.SS2.p2" class="ltx_para ltx_noindent">
<p id="S3.SS2.p2.1" class="ltx_p"><span id="S3.SS2.p2.1.1" class="ltx_text ltx_font_bold">Constraint Complexity Understanding
<br class="ltx_break"></span>To gain a better understanding of the planning ability of LLMs, we vary the difficulty level of each task through a controlled variable.
We conduct analysis by varying constraints such as number of people, number of cities, number of days etc. to better understand behavior of models across the variation in the complexity of the planning task.</p>
</div>
<div id="S3.SS2.p3" class="ltx_para ltx_noindent">
<p id="S3.SS2.p3.1" class="ltx_p"><span id="S3.SS2.p3.1.1" class="ltx_text ltx_font_bold">Few-Shot Generalization
<br class="ltx_break"></span>We conduct easy-to-hard and hard-to-easy generalization study by providing easier and harder examples as in-context exemplars, respectively. For instance, for easy-to-hard (hard-to-easy) generalization in <span id="S3.SS2.p3.1.2" class="ltx_text ltx_font_italic">Trip Planning</span>, we provide 5 easier (harder) examples with 2 fewer (more) cities than the ones in the evaluation task instances.</p>
</div>
<div id="S3.SS2.p4" class="ltx_para ltx_noindent">
<p id="S3.SS2.p4.1" class="ltx_p"><span id="S3.SS2.p4.1.1" class="ltx_text ltx_font_bold">Self-Correction
<br class="ltx_break"></span>We evaluate if models can self-correct their mistakes across various categories of tasks in <span id="S3.SS2.p4.1.2" class="ltx_text ltx_font_smallcaps">Natural Plan</span>. Here we prompt the model to identify if there are any mistakes and self correct if necessary.</p>
</div>
<div id="S3.SS2.p5" class="ltx_para ltx_noindent">
<p id="S3.SS2.p5.1" class="ltx_p"><span id="S3.SS2.p5.1.1" class="ltx_text ltx_font_bold">In-Context Planning with Long Context
<br class="ltx_break"></span>We evaluate how well models can leverage the long-context capabilities for in-context learning in planning. We split the test-set into 80% and 20%, where 80% is used as in-context examples while we evaluate the model performance on 20% of the test-set. We increase the number of few-shot examples used up to 800.</p>
</div>
<div id="S3.SS2.p6" class="ltx_para ltx_noindent">
<p id="S3.SS2.p6.1" class="ltx_p"><span id="S3.SS2.p6.1.1" class="ltx_text ltx_font_bold">Evaluation
<br class="ltx_break"></span>We parse the output from the LLM, and compare it with the golden plan. We compute an exact match (EM) score of the LLM-generated plan being identical to the golden plan. See Appendix <a href="#A3" title="Appendix C Plan Parsing and Scoring ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">C</span></a> for the details of parsing and scoring.</p>
</div>
</section>
</section>
<section id="S4" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">4 </span>Results and Analysis</h2>

<figure id="S4.T2" class="ltx_table">
<figcaption class="ltx_caption"><span class="ltx_tag ltx_tag_table">Table 2: </span>Accuracy of 5 models on <span id="S4.T2.2.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span>.
</figcaption>
<table id="S4.T2.3" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="S4.T2.3.1" class="ltx_tr">
<td id="S4.T2.3.1.1" class="ltx_td ltx_align_right ltx_border_r ltx_border_tt">Task</td>
<td id="S4.T2.3.1.2" class="ltx_td ltx_align_center ltx_border_r ltx_border_tt">GPT-3.5</td>
<td id="S4.T2.3.1.3" class="ltx_td ltx_align_center ltx_border_r ltx_border_tt">GPT-4</td>
<td id="S4.T2.3.1.4" class="ltx_td ltx_align_center ltx_border_r ltx_border_tt">GPT-4o</td>
<td id="S4.T2.3.1.5" class="ltx_td ltx_align_center ltx_border_r ltx_border_tt">Gemini 1.5 Flash</td>
<td id="S4.T2.3.1.6" class="ltx_td ltx_align_center ltx_border_tt">Gemini 1.5 Pro</td>
</tr>
<tr id="S4.T2.3.2" class="ltx_tr">
<td id="S4.T2.3.2.1" class="ltx_td ltx_align_right ltx_border_r ltx_border_t"><em id="S4.T2.3.2.1.1" class="ltx_emph ltx_font_italic">Trip Planning</em></td>
<td id="S4.T2.3.2.2" class="ltx_td ltx_align_center ltx_border_r ltx_border_t">7.3%</td>
<td id="S4.T2.3.2.3" class="ltx_td ltx_align_center ltx_border_r ltx_border_t">31.1%</td>
<td id="S4.T2.3.2.4" class="ltx_td ltx_align_center ltx_border_r ltx_border_t">3.7%</td>
<td id="S4.T2.3.2.5" class="ltx_td ltx_align_center ltx_border_r ltx_border_t">25.6%</td>
<td id="S4.T2.3.2.6" class="ltx_td ltx_align_center ltx_border_t"><span id="S4.T2.3.2.6.1" class="ltx_text ltx_font_bold">34.8%</span></td>
</tr>
<tr id="S4.T2.3.3" class="ltx_tr">
<td id="S4.T2.3.3.1" class="ltx_td ltx_align_right ltx_border_r"><em id="S4.T2.3.3.1.1" class="ltx_emph ltx_font_italic">Meeting Planning</em></td>
<td id="S4.T2.3.3.2" class="ltx_td ltx_align_center ltx_border_r">19.1%</td>
<td id="S4.T2.3.3.3" class="ltx_td ltx_align_center ltx_border_r"><span id="S4.T2.3.3.3.1" class="ltx_text ltx_font_bold">47.0%</span></td>
<td id="S4.T2.3.3.4" class="ltx_td ltx_align_center ltx_border_r">45.2%</td>
<td id="S4.T2.3.3.5" class="ltx_td ltx_align_center ltx_border_r">23.9%</td>
<td id="S4.T2.3.3.6" class="ltx_td ltx_align_center">39.1%</td>
</tr>
<tr id="S4.T2.3.4" class="ltx_tr">
<td id="S4.T2.3.4.1" class="ltx_td ltx_align_right ltx_border_bb ltx_border_r"><em id="S4.T2.3.4.1.1" class="ltx_emph ltx_font_italic">Calendar Scheduling</em></td>
<td id="S4.T2.3.4.2" class="ltx_td ltx_align_center ltx_border_bb ltx_border_r">19.9%</td>
<td id="S4.T2.3.4.3" class="ltx_td ltx_align_center ltx_border_bb ltx_border_r">41.2%</td>
<td id="S4.T2.3.4.4" class="ltx_td ltx_align_center ltx_border_bb ltx_border_r">43.7%</td>
<td id="S4.T2.3.4.5" class="ltx_td ltx_align_center ltx_border_bb ltx_border_r">34.3%</td>
<td id="S4.T2.3.4.6" class="ltx_td ltx_align_center ltx_border_bb"><span id="S4.T2.3.4.6.1" class="ltx_text ltx_font_bold">48.9%</span></td>
</tr>
</table>
</figure>
<section id="S4.SS1" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">4.1 </span>Results</h3>

<div id="S4.SS1.p1" class="ltx_para ltx_noindent">
<p id="S4.SS1.p1.1" class="ltx_p">Table <a href="#S4.T2" title="Table 2 ‣ 4 Results and Analysis ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">2</span></a> shows the performance of various LLMs across tasks in <span id="S4.SS1.p1.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span> in the 5-shot setup. We get the following insights from the results.</p>
</div>
<div id="S4.SS1.p2" class="ltx_para ltx_noindent">
<p id="S4.SS1.p2.1" class="ltx_p"><span id="S4.SS1.p2.1.1" class="ltx_text ltx_font_bold">All models perform poorly on <span id="S4.SS1.p2.1.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span>.</span> Gemini 1.5 Pro performs the best on <span id="S4.SS1.p2.1.2" class="ltx_text ltx_font_italic">Trip Planning</span> and <span id="S4.SS1.p2.1.3" class="ltx_text ltx_font_italic">Calendar Scheduling</span> while GPT-4 does the best on <span id="S4.SS1.p2.1.4" class="ltx_text ltx_font_italic">Meeting Planning</span>.</p>
</div>
<div id="S4.SS1.p3" class="ltx_para ltx_noindent">
<p id="S4.SS1.p3.1" class="ltx_p">In <em id="S4.SS1.p3.1.1" class="ltx_emph ltx_font_italic">Trip Planning</em>, Gemini 1.5 Pro achieves 34.8% accuracy while GPT-4 is 31.1%. In particular, we observe that GPT-4o is only at 3.7%. Further analysis shows that GPT-4o is struggling to understand and respect the flight connectivity and travel date constraints, see Appendix <a href="#A4" title="Appendix D Analysis of GPT-4o on Trip Planning ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">D</span></a> for a more detailed analysis.
GPT-4 and GPT-4o achieve 47% and 45.2% accuracy on <span id="S4.SS1.p3.1.2" class="ltx_text ltx_font_italic">Meeting Planning</span> while Gemini 1.5 Pro is 39.1%. For <span id="S4.SS1.p3.1.3" class="ltx_text ltx_font_italic">Calendar Scheduling</span>, Gemini 1.5 Pro outperforms GPT-4 and GPT-4o at 48.9%.</p>
</div>
<div id="S4.SS1.p4" class="ltx_para ltx_noindent">
<p id="S4.SS1.p4.1" class="ltx_p">Comparing the three tasks in <span id="S4.SS1.p4.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span>, <em id="S4.SS1.p4.1.2" class="ltx_emph ltx_font_italic">Trip Planning</em> is the hardest among them with the lowest best accuracy of 34.8%. Note all models have accuracy below 50% on all three tasks in <span id="S4.SS1.p4.1.3" class="ltx_text ltx_font_smallcaps">Natural Plan</span>, highlighting that planning in natural language is still a very challenging task even for the state of the art models, despite that all tool-use information needed is provided in the context.</p>
</div>
</section>
<section id="S4.SS2" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">4.2 </span>Constraint Complexity</h3>

<div id="S4.SS2.p1" class="ltx_para">
<p id="S4.SS2.p1.1" class="ltx_p">Figures <a href="#S4.F4" title="Figure 4 ‣ 4.2 Constraint Complexity ‣ 4 Results and Analysis ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">4</span></a>- <a href="#S4.F6" title="Figure 6 ‣ 4.2 Constraint Complexity ‣ 4 Results and Analysis ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">6</span></a> show the performance variation of models across variation in number of cities in <span id="S4.SS2.p1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span>, number of people in <span id="S4.SS2.p1.1.2" class="ltx_text ltx_font_italic">Meeting Scheduling</span>, and number of attendees/days in <span id="S4.SS2.p1.1.3" class="ltx_text ltx_font_italic">Calendar Scheduling</span> . We observe the following key insights:</p>
</div>
<figure id="S4.F4" class="ltx_figure"><img src="/html/2406.04520/assets/x1.png" id="S4.F4.1.g1" class="ltx_graphics ltx_centering ltx_img_landscape" width="461" height="212" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">Figure 4: </span>Constraint complexity analysis of the <span id="S4.F4.4.1" class="ltx_text ltx_font_italic">Trip Planning</span> task in <span id="S4.F4.5.2" class="ltx_text ltx_font_smallcaps">Natural Plan</span> as a function of number of cities.</figcaption>
</figure>
<figure id="S4.F5" class="ltx_figure"><img src="/html/2406.04520/assets/x2.png" id="S4.F5.1.g1" class="ltx_graphics ltx_centering ltx_img_landscape" width="461" height="212" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">Figure 5: </span>Constraint complexity analysis of the <span id="S4.F5.4.1" class="ltx_text ltx_font_italic">Meeting Planning</span> task in <span id="S4.F5.5.2" class="ltx_text ltx_font_smallcaps">Natural Plan</span> as a function of number of people.</figcaption>
</figure>
<figure id="S4.F6" class="ltx_figure"><img src="/html/2406.04520/assets/x3.png" id="S4.F6.1.g1" class="ltx_graphics ltx_centering ltx_img_landscape" width="461" height="186" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">Figure 6: </span>Constraint complexity analysis of the <span id="S4.F6.3.1" class="ltx_text ltx_font_italic">Calendar Scheduling</span> task as a function of the number of people involved to meet during a single day (left), and number of working days to choose a meeting time from between two attendees (right).</figcaption>
</figure>
<div id="S4.SS2.p2" class="ltx_para ltx_noindent">
<p id="S4.SS2.p2.1" class="ltx_p"><span id="S4.SS2.p2.1.1" class="ltx_text ltx_font_bold">Model performance reduces significantly as the task complexity increases as number of cities/number of people/number of attendees/number of days increase.</span> For <span id="S4.SS2.p2.1.2" class="ltx_text ltx_font_italic">Trip Planning</span>, Figure <a href="#S4.F4" title="Figure 4 ‣ 4.2 Constraint Complexity ‣ 4 Results and Analysis ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">4</span></a> shows that models start to fail with more cities involved in the planning. In <span id="S4.SS2.p2.1.3" class="ltx_text ltx_font_italic">Trip Planning</span>, all five models perform below 5% when there are 10 cities. For <span id="S4.SS2.p2.1.4" class="ltx_text ltx_font_italic">Meeting Planning</span>, we evaluate scenarios with the number of people to meet from 1 to 10. Figure <a href="#S4.F5" title="Figure 5 ‣ 4.2 Constraint Complexity ‣ 4 Results and Analysis ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">5</span></a> again shows that the performance drops sharply with more people to meet. Beyond 8 people, all models have a score lower than 10%. For <span id="S4.SS2.p2.1.5" class="ltx_text ltx_font_italic">Calendar Scheduling</span>, the drop of accuracy is not as significant when increasing number of attendees or number of days compared to the other two tasks.</p>
</div>
</section>
<section id="S4.SS3" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">4.3 </span>Generalization Analysis</h3>

<figure id="S4.F7" class="ltx_figure"><img src="/html/2406.04520/assets/x4.png" id="S4.F7.1.g1" class="ltx_graphics ltx_centering ltx_img_landscape" width="461" height="193" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">Figure 7: </span>Model performance on the <span id="S4.F7.3.1" class="ltx_text ltx_font_italic">Trip Planning</span> task as a function of number of cities for few-shot generalization ablations: E2H=easy-to-hard, H2E=hard-to-easy.</figcaption>
</figure>
<div id="S4.SS3.p1" class="ltx_para ltx_noindent">
<p id="S4.SS3.p1.1" class="ltx_p">Figure <a href="#S4.F7" title="Figure 7 ‣ 4.3 Generalization Analysis ‣ 4 Results and Analysis ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">7</span></a> shows the summary of our easy-to-hard and hard-to-easy generalization experiments. For easy-to-hard (hard-to-easy) generalization, we present 5 easier (harder) examples with 2 fewer (more) cities than the task, to test whether LLMs can generalize from easier (harder) in-context learning examples. We choose <span id="S4.SS3.p1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span> to conduct our ablations on given that it is the most difficult task among <span id="S4.SS3.p1.1.2" class="ltx_text ltx_font_smallcaps">Natural Plan</span> tasks.</p>
</div>
<div id="S4.SS3.p2" class="ltx_para ltx_noindent">
<p id="S4.SS3.p2.1" class="ltx_p"><span id="S4.SS3.p2.1.1" class="ltx_text ltx_font_bold">In general, we observe that easy-to-hard performs better than hard-to-easy generalization across model families.</span> Section <a href="#S4.SS2" title="4.2 Constraint Complexity ‣ 4 Results and Analysis ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">4.2</span></a> shows models perform worse when the task complexity is higher. This result indicates that understanding and making use of hard demonstrations in in-context learning is still challenging even for state of the art LLMs. However, we do observe that for GPT-4 and Gemini 1.5 Flash, the trend is reversed as the task complexity increases: for <math id="S4.SS3.p2.1.m1.1" class="ltx_Math" alttext="N=5\sim 8" display="inline"><semantics id="S4.SS3.p2.1.m1.1a"><mrow id="S4.SS3.p2.1.m1.1.1" xref="S4.SS3.p2.1.m1.1.1.cmml"><mi id="S4.SS3.p2.1.m1.1.1.2" xref="S4.SS3.p2.1.m1.1.1.2.cmml">N</mi><mo id="S4.SS3.p2.1.m1.1.1.3" xref="S4.SS3.p2.1.m1.1.1.3.cmml">=</mo><mn id="S4.SS3.p2.1.m1.1.1.4" xref="S4.SS3.p2.1.m1.1.1.4.cmml">5</mn><mo id="S4.SS3.p2.1.m1.1.1.5" xref="S4.SS3.p2.1.m1.1.1.5.cmml">∼</mo><mn id="S4.SS3.p2.1.m1.1.1.6" xref="S4.SS3.p2.1.m1.1.1.6.cmml">8</mn></mrow><annotation-xml encoding="MathML-Content" id="S4.SS3.p2.1.m1.1b"><apply id="S4.SS3.p2.1.m1.1.1.cmml" xref="S4.SS3.p2.1.m1.1.1"><and id="S4.SS3.p2.1.m1.1.1a.cmml" xref="S4.SS3.p2.1.m1.1.1"></and><apply id="S4.SS3.p2.1.m1.1.1b.cmml" xref="S4.SS3.p2.1.m1.1.1"><eq id="S4.SS3.p2.1.m1.1.1.3.cmml" xref="S4.SS3.p2.1.m1.1.1.3"></eq><ci id="S4.SS3.p2.1.m1.1.1.2.cmml" xref="S4.SS3.p2.1.m1.1.1.2">𝑁</ci><cn type="integer" id="S4.SS3.p2.1.m1.1.1.4.cmml" xref="S4.SS3.p2.1.m1.1.1.4">5</cn></apply><apply id="S4.SS3.p2.1.m1.1.1c.cmml" xref="S4.SS3.p2.1.m1.1.1"><csymbol cd="latexml" id="S4.SS3.p2.1.m1.1.1.5.cmml" xref="S4.SS3.p2.1.m1.1.1.5">similar-to</csymbol><share href="#S4.SS3.p2.1.m1.1.1.4.cmml" id="S4.SS3.p2.1.m1.1.1d.cmml" xref="S4.SS3.p2.1.m1.1.1"></share><cn type="integer" id="S4.SS3.p2.1.m1.1.1.6.cmml" xref="S4.SS3.p2.1.m1.1.1.6">8</cn></apply></apply></annotation-xml><annotation encoding="application/x-tex" id="S4.SS3.p2.1.m1.1c">N=5\sim 8</annotation></semantics></math>, hard-to-easy demonstrations work better than easy-to-hard.</p>
</div>
</section>
<section id="S4.SS4" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">4.4 </span>Self-Correction</h3>

<figure id="S4.F8" class="ltx_figure"><img src="/html/2406.04520/assets/x5.png" id="S4.F8.1.g1" class="ltx_graphics ltx_centering ltx_img_landscape" width="461" height="193" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">Figure 8: </span>Accuracy of <span id="S4.F8.3.1" class="ltx_text ltx_font_italic">Trip Planning</span> as a function of number of cities for self-correction ablations. SC=self-correction</figcaption>
</figure>
<div id="S4.SS4.p1" class="ltx_para ltx_noindent">
<p id="S4.SS4.p1.1" class="ltx_p">Figure <a href="#S4.F8" title="Figure 8 ‣ 4.4 Self-Correction ‣ 4 Results and Analysis ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">8</span></a> shows the results of performing self-correction on model predictions in the <span id="S4.SS4.p1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span> task. We prompt the LLM to check whether the generated plan is correct or not, and if determined incorrect, fix the plan (see Appendix <a href="#A2" title="Appendix B Prompts ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">B</span></a> for the prompt).</p>
</div>
<div id="S4.SS4.p2" class="ltx_para ltx_noindent">
<p id="S4.SS4.p2.1" class="ltx_p"><span id="S4.SS4.p2.1.1" class="ltx_text ltx_font_bold">Self-correction leads to significant model performance drop across all models. Interestingly, the stronger models such as GPT-4 and Gemini 1.5 Pro suffer bigger loss compared to GPT-3.5.</span> This aligns well with previous findings that self-correction could lead to performance degradation on Reasoning <cite class="ltx_cite ltx_citemacro_citep">(Huang et al., <a href="#bib.bib15" title="" class="ltx_ref">2023</a>)</cite>. The stronger instruction-tuned models like GPT-4 and Gemini 1.5 Pro could be over-confident towards correcting its own solutions when prompted, see Appendix <a href="#A5" title="Appendix E Self-Correction Example ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">E</span></a> for examples of self-correction.</p>
</div>
</section>
<section id="S4.SS5" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">4.5 </span>In-Context Planning with Long Context</h3>

<figure id="S4.F9" class="ltx_figure"><img src="/html/2406.04520/assets/x6.png" id="S4.F9.1.g1" class="ltx_graphics ltx_centering ltx_img_landscape" width="461" height="210" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">Figure 9: </span>In-Context planning with long context for <span id="S4.F9.4.1" class="ltx_text ltx_font_italic">Trip Planning</span> and <span id="S4.F9.5.2" class="ltx_text ltx_font_italic">Calendar Scheduling</span> tasks. Gemini 1.5 Pro shows strong long-context learning on Planning compared to other models.</figcaption>
</figure>
<div id="S4.SS5.p1" class="ltx_para ltx_noindent">
<p id="S4.SS5.p1.1" class="ltx_p">In this section, we study the possibility of in-context planning by leveraging the long context capabilities of recent models <cite class="ltx_cite ltx_citemacro_citep">(Gemini Team, <a href="#bib.bib9" title="" class="ltx_ref">2024</a>)</cite>. Figure <a href="#S4.F9" title="Figure 9 ‣ 4.5 In-Context Planning with Long Context ‣ 4 Results and Analysis ‣ Natural Plan: Benchmarking LLMs on Natural Language Planning" class="ltx_ref"><span class="ltx_text ltx_ref_tag">9</span></a> shows the performance of four models up to 800 shots.</p>
</div>
<div id="S4.SS5.p2" class="ltx_para ltx_noindent">
<p id="S4.SS5.p2.1" class="ltx_p"><span id="S4.SS5.p2.1.1" class="ltx_text ltx_font_bold">Due to the strong long context capabilities, Gemini Pro 1.5 is able to leverage more in-context examples up to 355K tokens, still showing steady improvements.</span> For instance, in <span id="S4.SS5.p2.1.2" class="ltx_text ltx_font_italic">Trip Planning</span>, increasing number of shots from 1 to 800 brings up the accuracy of Gemini Pro 1.5 from 2.7% to 39.9%. In the mean time, both GPT-4 and Gemini 1.5 Flash peak at 20-shot and start to show performance degradation. The same is observed in <span id="S4.SS5.p2.1.3" class="ltx_text ltx_font_italic">Calendar Scheduling</span> where Gemini 1.5 Pro continually improves up to 400 shots. These results show the promise of in-context planning where the long-context capabilities enable LLMs to leverage further context to improve Planning.</p>
</div>
</section>
</section>
<section id="S5" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">5 </span>Related Works</h2>

<div id="S5.p1" class="ltx_para ltx_noindent">
<p id="S5.p1.1" class="ltx_p">Planning empowers intelligent agents to look ahead and proactively determine a course of action to reach objectives <cite class="ltx_cite ltx_citemacro_citep">(McCarthy et al., <a href="#bib.bib22" title="" class="ltx_ref">1963</a>; Russell and Norvig, <a href="#bib.bib24" title="" class="ltx_ref">2016</a>)</cite>. Automated/classical planning is a subarea of AI that allows sequential decision-making systems to choose a sequence of actions using which they complete a (set of) task(s) autonomously <cite class="ltx_cite ltx_citemacro_citep">(Ghallab et al., <a href="#bib.bib10" title="" class="ltx_ref">2004</a>)</cite>. Most of the planning formalisms use a Planning Domain Definition Language (PDDL) <cite class="ltx_cite ltx_citemacro_citep">(McDermott et al., <a href="#bib.bib23" title="" class="ltx_ref">1998</a>)</cite>, where it separates the environment dynamics (domain definition) from the environment configuration (problem definition). Domain-independent planners like Fast-Forward <cite class="ltx_cite ltx_citemacro_citep">(Hoffmann and Nebel, <a href="#bib.bib14" title="" class="ltx_ref">2001</a>)</cite>, Fast-Downward <cite class="ltx_cite ltx_citemacro_citep">(Helmert, <a href="#bib.bib13" title="" class="ltx_ref">2006</a>)</cite>, etc. take these domain and problem definitions as input and generate a sequence of actions that takes a planning agent from a given initial state to a state satisfying a goal condition (also given as input with the problem definition). Such classical planning methods
have been widely adopted in robots and embodied environments <cite class="ltx_cite ltx_citemacro_citep">(Camacho et al., <a href="#bib.bib4" title="" class="ltx_ref">2007</a>; Jiang et al., <a href="#bib.bib17" title="" class="ltx_ref">2019a</a>)</cite>.
Most planning benchmarks <span id="footnote1" class="ltx_note ltx_role_footnote"><sup class="ltx_note_mark">1</sup><span class="ltx_note_outer"><span class="ltx_note_content"><sup class="ltx_note_mark">1</sup><span class="ltx_tag ltx_tag_note">1</span>https://www.icaps-conference.org/competitions/</span></span></span> use similar formulations with variations like probabilities <cite class="ltx_cite ltx_citemacro_citep">(Younes et al., <a href="#bib.bib33" title="" class="ltx_ref">2005</a>)</cite>, numeric fluents <span id="footnote2" class="ltx_note ltx_role_footnote"><sup class="ltx_note_mark">2</sup><span class="ltx_note_outer"><span class="ltx_note_content"><sup class="ltx_note_mark">2</sup><span class="ltx_tag ltx_tag_note">2</span>https://ipc2023-numeric.github.io/</span></span></span>, temporal actions, etc. as benchmarks. The main issue with such benchmarks is that they are not expressed in natural language and hence need experts to handcraft the domains and problems.</p>
</div>
<div id="S5.p2" class="ltx_para ltx_noindent">
<p id="S5.p2.1" class="ltx_p">Recently prompting LLMs to extract common sense knowledge gained attention <cite class="ltx_cite ltx_citemacro_citep">(Huang et al., <a href="#bib.bib16" title="" class="ltx_ref">2022</a>; Singh et al., <a href="#bib.bib26" title="" class="ltx_ref">2023</a>; Ding et al., <a href="#bib.bib8" title="" class="ltx_ref">2023</a>)</cite>. Effectiveness of LLMs in generating plans has been studied by <cite class="ltx_cite ltx_citemacro_cite">Valmeekam et al. (<a href="#bib.bib29" title="" class="ltx_ref">2024</a>); Hao et al. (<a href="#bib.bib12" title="" class="ltx_ref">2023</a>); Guan et al. (<a href="#bib.bib11" title="" class="ltx_ref">2024</a>)</cite>. While <cite class="ltx_cite ltx_citemacro_cite">Valmeekam et al. (<a href="#bib.bib29" title="" class="ltx_ref">2024</a>); Guan et al. (<a href="#bib.bib11" title="" class="ltx_ref">2024</a>)</cite> translate natural language instructions into the executable programming languages, such as PDDL, and runs classical planning algorithms, <cite class="ltx_cite ltx_citemacro_cite">Hao et al. (<a href="#bib.bib12" title="" class="ltx_ref">2023</a>)</cite> uses the LLM as both a world model and a reasoning agent, enhanced by a Monte Carlo Tree Search algorithm for efficient exploration.</p>
</div>
<div id="S5.p3" class="ltx_para ltx_noindent">
<p id="S5.p3.1" class="ltx_p">Even though these works target to improve the planning capability of LLMs, these are not able to perform well in more complex and realistic settings, closer to those in which humans operate <cite class="ltx_cite ltx_citemacro_citep">(Valmeekam et al., <a href="#bib.bib28" title="" class="ltx_ref">2022</a>)</cite>. TravelPlanner <cite class="ltx_cite ltx_citemacro_citep">(Xie et al., <a href="#bib.bib32" title="" class="ltx_ref">2024</a>)</cite> provides a sandbox with various tools to evaluate language model capabilities in performing planning via agents. Our work <span id="S5.p3.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span> provides a holistic benchmark in natural language to evaluate the planning capability of models in real world tasks.</p>
</div>
</section>
<section id="S6" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">6 </span>Conclusion</h2>

<div id="S6.p1" class="ltx_para ltx_noindent">
<p id="S6.p1.1" class="ltx_p">We introduce <span id="S6.p1.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span> to evaluate the capability of LLMs to plan on real world tasks given in natural language. <span id="S6.p1.1.2" class="ltx_text ltx_font_smallcaps">Natural Plan</span> covers three domains: <span id="S6.p1.1.3" class="ltx_text ltx_font_italic">Trip Planning</span>, <span id="S6.p1.1.4" class="ltx_text ltx_font_italic">Calendar Scheduling</span>, and <span id="S6.p1.1.5" class="ltx_text ltx_font_italic">Meeting Planning</span>. The tasks also contain API results from various tools such as Google Calendar, Google Flights and Google Maps mimicking real world planning tasks with tools. We find that <span id="S6.p1.1.6" class="ltx_text ltx_font_smallcaps">Natural Plan</span> is very hard for state of the art models to solve. Models increasingly struggle as the complexity of the problem increases, e.g. an increase in number of people, cities or days in the question. However, our in-context planning experiments demonstrate the potential promise of leveraging the long-context capabilities to boost LLMs’ planning ability.</p>
</div>
<section id="S6.SS0.SSSx1" class="ltx_subsubsection">
<h4 class="ltx_title ltx_title_subsubsection">Acknowledgments</h4>

<div id="S6.SS0.SSSx1.p1" class="ltx_para ltx_noindent">
<p id="S6.SS0.SSSx1.p1.1" class="ltx_p">We acknowledge careful review and feedback from Uri Alon and Aleksandra Faust of Google DeepMind on the draft of this paper.</p>
</div>
</section>
</section>
<section id="bib" class="ltx_bibliography">
<h2 class="ltx_title ltx_title_bibliography">References</h2>

<ul class="ltx_biblist">
<li id="bib.bib1" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Achiam et al. (2023)</span>
<span class="ltx_bibblock">
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya,
Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman,
Shyamal Anadkat, et al.

</span>
<span class="ltx_bibblock">Gpt-4 technical report.

</span>
<span class="ltx_bibblock"><em id="bib.bib1.1.1" class="ltx_emph ltx_font_italic">arXiv preprint arXiv:2303.08774</em>, 2023.

</span>
</li>
<li id="bib.bib2" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Brewka et al. (2011)</span>
<span class="ltx_bibblock">
Gerhard Brewka, Thomas Eiter, and Mirosław Truszczyński.

</span>
<span class="ltx_bibblock">Answer set programming at a glance.

</span>
<span class="ltx_bibblock"><em id="bib.bib2.1.1" class="ltx_emph ltx_font_italic">Communications of the ACM</em>, 54(12):92–103,
2011.

</span>
</li>
<li id="bib.bib3" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Brown et al. (2020)</span>
<span class="ltx_bibblock">
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla
Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell,
et al.

</span>
<span class="ltx_bibblock">Language models are few-shot learners.

</span>
<span class="ltx_bibblock"><em id="bib.bib3.1.1" class="ltx_emph ltx_font_italic">Advances in neural information processing systems</em>,
33:1877–1901, 2020.

</span>
</li>
<li id="bib.bib4" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Camacho et al. (2007)</span>
<span class="ltx_bibblock">
Eduardo F Camacho, Carlos Bordons, Eduardo F Camacho, and Carlos Bordons.

</span>
<span class="ltx_bibblock"><em id="bib.bib4.1.1" class="ltx_emph ltx_font_italic">Constrained model predictive control</em>.

</span>
<span class="ltx_bibblock">Springer, 2007.

</span>
</li>
<li id="bib.bib5" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Chen et al. (2021)</span>
<span class="ltx_bibblock">
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira
Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg
Brockman, et al.

</span>
<span class="ltx_bibblock">Evaluating large language models trained on code.

</span>
<span class="ltx_bibblock"><em id="bib.bib5.1.1" class="ltx_emph ltx_font_italic">arXiv preprint arXiv:2107.03374</em>, 2021.

</span>
</li>
<li id="bib.bib6" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Cobbe et al. (2021)</span>
<span class="ltx_bibblock">
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz
Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano,
et al.

</span>
<span class="ltx_bibblock">Training verifiers to solve math word problems.

</span>
<span class="ltx_bibblock"><em id="bib.bib6.1.1" class="ltx_emph ltx_font_italic">arXiv preprint arXiv:2110.14168</em>, 2021.

</span>
</li>
<li id="bib.bib7" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Ding et al. (2020)</span>
<span class="ltx_bibblock">
Yan Ding, Xiaohan Zhang, Xingyue Zhan, and Shiqi Zhang.

</span>
<span class="ltx_bibblock">Task-motion planning for safe and efficient urban driving.

</span>
<span class="ltx_bibblock">In <em id="bib.bib7.1.1" class="ltx_emph ltx_font_italic">2020 IEEE/RSJ International Conference on Intelligent Robots
and Systems (IROS)</em>, pages 2119–2125. IEEE, 2020.

</span>
</li>
<li id="bib.bib8" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Ding et al. (2023)</span>
<span class="ltx_bibblock">
Yan Ding, Xiaohan Zhang, Chris Paxton, and Shiqi Zhang.

</span>
<span class="ltx_bibblock">Task and motion planning with large language models for object
rearrangement.

</span>
<span class="ltx_bibblock">In <em id="bib.bib8.1.1" class="ltx_emph ltx_font_italic">2023 IEEE/RSJ International Conference on Intelligent Robots
and Systems (IROS)</em>, pages 2086–2092. IEEE, 2023.

</span>
</li>
<li id="bib.bib9" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Gemini Team (2024)</span>
<span class="ltx_bibblock">
Google Gemini Team.

</span>
<span class="ltx_bibblock">Gemini 1.5: Unlocking multimodal understanding across millions of
tokens of context, 2024.

</span>
</li>
<li id="bib.bib10" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Ghallab et al. (2004)</span>
<span class="ltx_bibblock">
Malik Ghallab, Dana Nau, and Paolo Traverso.

</span>
<span class="ltx_bibblock"><em id="bib.bib10.1.1" class="ltx_emph ltx_font_italic">Automated Planning: Theory and Practice</em>.

</span>
<span class="ltx_bibblock">Morgan Kaufmann, Amsterdam, 2004.

</span>
<span class="ltx_bibblock">ISBN 978-1-55860-856-6.

</span>
<span class="ltx_bibblock">URL <a target="_blank" href="http://www.sciencedirect.com/science/book/9781558608566" title="" class="ltx_ref ltx_url ltx_font_typewriter">http://www.sciencedirect.com/science/book/9781558608566</a>.

</span>
</li>
<li id="bib.bib11" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Guan et al. (2024)</span>
<span class="ltx_bibblock">
Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati.

</span>
<span class="ltx_bibblock">Leveraging pre-trained large language models to construct and utilize
world models for model-based task planning.

</span>
<span class="ltx_bibblock"><em id="bib.bib11.1.1" class="ltx_emph ltx_font_italic">Advances in Neural Information Processing Systems</em>, 36, 2024.

</span>
</li>
<li id="bib.bib12" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Hao et al. (2023)</span>
<span class="ltx_bibblock">
Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and
Zhiting Hu.

</span>
<span class="ltx_bibblock">Reasoning with language model is planning with world model.

</span>
<span class="ltx_bibblock"><em id="bib.bib12.1.1" class="ltx_emph ltx_font_italic">arXiv preprint arXiv:2305.14992</em>, 2023.

</span>
</li>
<li id="bib.bib13" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Helmert (2006)</span>
<span class="ltx_bibblock">
Malte Helmert.

</span>
<span class="ltx_bibblock">The fast downward planning system.

</span>
<span class="ltx_bibblock"><em id="bib.bib13.1.1" class="ltx_emph ltx_font_italic">Journal of Artificial Intelligence Research</em>, 26:191–246, 2006.

</span>
</li>
<li id="bib.bib14" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Hoffmann and Nebel (2001)</span>
<span class="ltx_bibblock">
Jörg Hoffmann and Bernhard Nebel.

</span>
<span class="ltx_bibblock">The FF Planning System: Fast Plan Generation Through Heuristic
Search.

</span>
<span class="ltx_bibblock"><em id="bib.bib14.1.1" class="ltx_emph ltx_font_italic">Journal of Artificial Intelligence Research</em>, 14:253–302, 2001.

</span>
</li>
<li id="bib.bib15" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Huang et al. (2023)</span>
<span class="ltx_bibblock">
Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu,
Xinying Song, and Denny Zhou.

</span>
<span class="ltx_bibblock">Large language models cannot self-correct reasoning yet.

</span>
<span class="ltx_bibblock">In <em id="bib.bib15.1.1" class="ltx_emph ltx_font_italic">The Twelfth International Conference on Learning
Representations</em>, 2023.

</span>
</li>
<li id="bib.bib16" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Huang et al. (2022)</span>
<span class="ltx_bibblock">
Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy
Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, et al.

</span>
<span class="ltx_bibblock">Inner monologue: Embodied reasoning through planning with language
models.

</span>
<span class="ltx_bibblock"><em id="bib.bib16.1.1" class="ltx_emph ltx_font_italic">arXiv preprint arXiv:2207.05608</em>, 2022.

</span>
</li>
<li id="bib.bib17" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Jiang et al. (2019a)</span>
<span class="ltx_bibblock">
Yu-qian Jiang, Shi-qi Zhang, Piyush Khandelwal, and Peter Stone.

</span>
<span class="ltx_bibblock">Task planning in robotics: an empirical comparison of pddl-and
asp-based systems.

</span>
<span class="ltx_bibblock"><em id="bib.bib17.1.1" class="ltx_emph ltx_font_italic">Frontiers of Information Technology &amp; Electronic Engineering</em>,
20:363–373, 2019a.

</span>
</li>
<li id="bib.bib18" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Jiang et al. (2019b)</span>
<span class="ltx_bibblock">
Yuqian Jiang, Harel Yedidsion, Shiqi Zhang, Guni Sharon, and Peter Stone.

</span>
<span class="ltx_bibblock">Multi-robot planning with conflicts and synergies.

</span>
<span class="ltx_bibblock"><em id="bib.bib18.1.1" class="ltx_emph ltx_font_italic">Autonomous Robots</em>, 43(8):2011–2032,
2019b.

</span>
</li>
<li id="bib.bib19" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Lagriffoul et al. (2018)</span>
<span class="ltx_bibblock">
Fabien Lagriffoul, Neil T Dantam, Caelan Garrett, Aliakbar Akbari, Siddharth
Srivastava, and Lydia E Kavraki.

</span>
<span class="ltx_bibblock">Platform-independent benchmarks for task and motion planning.

</span>
<span class="ltx_bibblock"><em id="bib.bib19.1.1" class="ltx_emph ltx_font_italic">IEEE Robotics and Automation Letters</em>, 3(4):3765–3772, 2018.

</span>
</li>
<li id="bib.bib20" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">LaValle (2006)</span>
<span class="ltx_bibblock">
Steven M. LaValle.

</span>
<span class="ltx_bibblock"><em id="bib.bib20.1.1" class="ltx_emph ltx_font_italic">Planning Algorithms</em>.

</span>
<span class="ltx_bibblock">Cambridge University Press, 2006.

</span>
</li>
<li id="bib.bib21" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Liu et al. (2023)</span>
<span class="ltx_bibblock">
Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas,
and Peter Stone.

</span>
<span class="ltx_bibblock">Llm+ p: Empowering large language models with optimal planning
proficiency.

</span>
<span class="ltx_bibblock"><em id="bib.bib21.1.1" class="ltx_emph ltx_font_italic">arXiv preprint arXiv:2304.11477</em>, 2023.

</span>
</li>
<li id="bib.bib22" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">McCarthy et al. (1963)</span>
<span class="ltx_bibblock">
John McCarthy et al.

</span>
<span class="ltx_bibblock"><em id="bib.bib22.1.1" class="ltx_emph ltx_font_italic">Situations, actions, and causal laws</em>.

</span>
<span class="ltx_bibblock">Comtex Scientific, 1963.

</span>
</li>
<li id="bib.bib23" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">McDermott et al. (1998)</span>
<span class="ltx_bibblock">
Drew McDermott, Malik Ghallab, Adele Howe, Craig Knoblock, A. Ram, Manuela
Veloso, Daniel S. Weld, and David Wilkins.

</span>
<span class="ltx_bibblock">PDDL – The Planning Domain Definition Language.

</span>
<span class="ltx_bibblock">Technical Report CVC TR-98-003/DCS TR-1165, Yale Center for Comp.
Vision and Control, 1998.

</span>
</li>
<li id="bib.bib24" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Russell and Norvig (2016)</span>
<span class="ltx_bibblock">
Stuart J Russell and Peter Norvig.

</span>
<span class="ltx_bibblock"><em id="bib.bib24.1.1" class="ltx_emph ltx_font_italic">Artificial intelligence: a modern approach</em>.

</span>
<span class="ltx_bibblock">Pearson, 2016.

</span>
</li>
<li id="bib.bib25" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Silver et al. (2023)</span>
<span class="ltx_bibblock">
Tom Silver, Soham Dan, Kavitha Srinivas, Joshua B Tenenbaum, Leslie Pack
Kaelbling, and Michael Katz.

</span>
<span class="ltx_bibblock">Generalized planning in pddl domains with pretrained large language
models.

</span>
<span class="ltx_bibblock"><em id="bib.bib25.1.1" class="ltx_emph ltx_font_italic">arXiv preprint arXiv:2305.11014</em>, 2023.

</span>
</li>
<li id="bib.bib26" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Singh et al. (2023)</span>
<span class="ltx_bibblock">
Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan
Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg.

</span>
<span class="ltx_bibblock">Progprompt: Generating situated robot task plans using large language
models.

</span>
<span class="ltx_bibblock">In <em id="bib.bib26.1.1" class="ltx_emph ltx_font_italic">2023 IEEE International Conference on Robotics and
Automation (ICRA)</em>, pages 11523–11530. IEEE, 2023.

</span>
</li>
<li id="bib.bib27" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Team et al. (2023)</span>
<span class="ltx_bibblock">
Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac,
Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al.

</span>
<span class="ltx_bibblock">Gemini: a family of highly capable multimodal models.

</span>
<span class="ltx_bibblock"><em id="bib.bib27.1.1" class="ltx_emph ltx_font_italic">arXiv preprint arXiv:2312.11805</em>, 2023.

</span>
</li>
<li id="bib.bib28" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Valmeekam et al. (2022)</span>
<span class="ltx_bibblock">
Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati.

</span>
<span class="ltx_bibblock">Large language models still can’t plan (a benchmark for llms on
planning and reasoning about change).

</span>
<span class="ltx_bibblock"><em id="bib.bib28.1.1" class="ltx_emph ltx_font_italic">arXiv preprint arXiv:2206.10498</em>, 2022.

</span>
</li>
<li id="bib.bib29" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Valmeekam et al. (2024)</span>
<span class="ltx_bibblock">
Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao
Kambhampati.

</span>
<span class="ltx_bibblock">On the planning abilities of large language models-a critical
investigation.

</span>
<span class="ltx_bibblock"><em id="bib.bib29.1.1" class="ltx_emph ltx_font_italic">Advances in Neural Information Processing Systems</em>, 36, 2024.

</span>
</li>
<li id="bib.bib30" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Wang et al. (2023)</span>
<span class="ltx_bibblock">
Xinyuan Wang, Chenxi Li, Zhen Wang, Fan Bai, Haotian Luo, Jiayou Zhang, Nebojsa
Jojic, Eric P Xing, and Zhiting Hu.

</span>
<span class="ltx_bibblock">Promptagent: Strategic planning with language models enables
expert-level prompt optimization.

</span>
<span class="ltx_bibblock"><em id="bib.bib30.1.1" class="ltx_emph ltx_font_italic">arXiv preprint arXiv:2310.16427</em>, 2023.

</span>
</li>
<li id="bib.bib31" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Winograd (1972)</span>
<span class="ltx_bibblock">
Terry Winograd.

</span>
<span class="ltx_bibblock">Understanding natural language.

</span>
<span class="ltx_bibblock"><em id="bib.bib31.1.1" class="ltx_emph ltx_font_italic">Cognitive psychology</em>, 3(1):1–191, 1972.

</span>
</li>
<li id="bib.bib32" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Xie et al. (2024)</span>
<span class="ltx_bibblock">
Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian,
Yanghua Xiao, and Yu Su.

</span>
<span class="ltx_bibblock">Travelplanner: A benchmark for real-world planning with language
agents.

</span>
<span class="ltx_bibblock"><em id="bib.bib32.1.1" class="ltx_emph ltx_font_italic">arXiv preprint arXiv:2402.01622</em>, 2024.

</span>
</li>
<li id="bib.bib33" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Younes et al. (2005)</span>
<span class="ltx_bibblock">
Håkan LS Younes, Michael L Littman, David Weissman, and John Asmuth.

</span>
<span class="ltx_bibblock">The first probabilistic track of the international planning
competition.

</span>
<span class="ltx_bibblock"><em id="bib.bib33.1.1" class="ltx_emph ltx_font_italic">Journal of Artificial Intelligence Research</em>, 24:851–887, 2005.

</span>
</li>
<li id="bib.bib34" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Zhang et al. (2015)</span>
<span class="ltx_bibblock">
Shiqi Zhang, Fangkai Yang, Piyush Khandelwal, and Peter Stone.

</span>
<span class="ltx_bibblock">Mobile robot planning using action language with an abstraction
hierarchy.

</span>
<span class="ltx_bibblock">In <em id="bib.bib34.1.1" class="ltx_emph ltx_font_italic">International Conference on Logic Programming and
Nonmonotonic Reasoning</em>, pages 502–516. Springer, 2015.

</span>
</li>
</ul>
</section>
<section id="A1" class="ltx_appendix">
<h2 class="ltx_title ltx_title_appendix">
<span class="ltx_tag ltx_tag_appendix">Appendix A </span><span id="A1.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span> Examples</h2>

<div id="A1.p1" class="ltx_para ltx_noindent">
<p id="A1.p1.1" class="ltx_p">Below is one example pair of the prompt and solution for each task in <span id="A1.p1.1.1" class="ltx_text ltx_font_smallcaps">Natural Plan</span>.</p>
</div>
<div id="A1.p2" class="ltx_para ltx_noindent">
<svg id="A1.p2.pic1" class="ltx_picture" height="45341.08" overflow="visible" version="1.1" width="45341.08"><g transform="translate(0,45341.08) matrix(1 0 0 -1 0 0) translate(22670.54,0) translate(0,22670.54)" fill="#000000" stroke="#000000" stroke-width="0.4pt"><clipPath id="pgfcp13"><path d="M -22670.54 -22670.54 L 22670.54 -22670.54 L 22670.54 22670.54 L -22670.54 22670.54 Z M 0 5.91 L 0 299.34 C 0 302.6 2.64 305.25 5.91 305.25 L 594.09 305.25 C 597.36 305.25 600 302.6 600 299.34 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z"></path></clipPath><g fill-rule="evenodd"><g fill="#0000BF" fill-opacity="1.0"><path d="M 0 5.91 L 0 299.34 C 0 302.6 2.64 305.25 5.91 305.25 L 594.09 305.25 C 597.36 305.25 600 302.6 600 299.34 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z M 1.97 5.91 L 1.97 275.17 L 598.03 275.17 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill="#FFFFFF" fill-opacity="1.0"><path d="M 1.97 5.91 L 1.97 275.17 L 598.03 275.17 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 284.06)"><foreignObject width="568.39" height="12.3" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#FFFFFF">
<span id="A1.p2.pic1.1.1.1.1.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A1.p2.pic1.1.1.1.1.1.1.1" class="ltx_p"><span id="A1.p2.pic1.1.1.1.1.1.1.1.1" class="ltx_text ltx_font_bold ltx_font_italic">Trip Planning</span></span>
</span></foreignObject></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 15.81)"><foreignObject width="568.39" height="245.53" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#000000">
<span id="A1.p2.pic1.2.2.2.2.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A1.p2.pic1.2.2.2.2.1.1.1" class="ltx_p"><span id="A1.p2.pic1.2.2.2.2.1.1.1.1" class="ltx_text ltx_font_bold">Prompt:
<br class="ltx_break"></span>You plan to visit 3 European cities for 14 days in total. You only take direct flights to commute between cities. You would like to visit Florence for 6 days. You want to meet a friend in Florence between day 9 and day 14. You would like to visit Barcelona for 5 days. You would like to visit Helsinki for 5 days.</span>
<span id="A1.p2.pic1.2.2.2.2.1.1.2" class="ltx_p">Here are the cities that have direct flights: Barcelona and Florence, Helsinki and Barcelona.</span>
<span id="A1.p2.pic1.2.2.2.2.1.1.3" class="ltx_p">Find a trip plan of visiting the cities for 14 days by taking direct flights to commute between them.</span>
<span id="A1.p2.pic1.2.2.2.2.1.1.4" class="ltx_p"><span id="A1.p2.pic1.2.2.2.2.1.1.4.1" class="ltx_text ltx_font_bold">Solution:</span></span>
<span id="A1.p2.pic1.2.2.2.2.1.1.5" class="ltx_p">Here is the trip plan for visiting the 3 European cities for 14 days:</span>
<span id="A1.p2.pic1.2.2.2.2.1.1.6" class="ltx_p">**Day 1-5:** Arriving in Helsinki and visit Helsinki for 5 days.</span>
<span id="A1.p2.pic1.2.2.2.2.1.1.7" class="ltx_p">**Day 5:** Fly from Helsinki to Barcelona.</span>
<span id="A1.p2.pic1.2.2.2.2.1.1.8" class="ltx_p">**Day 5-9:** Visit Barcelona for 5 days.</span>
<span id="A1.p2.pic1.2.2.2.2.1.1.9" class="ltx_p">**Day 9:** Fly from Barcelona to Florence.</span>
<span id="A1.p2.pic1.2.2.2.2.1.1.10" class="ltx_p">**Day 9-14:** Visit Florence for 6 days.</span>
</span></foreignObject></g></g></g></svg>
</div>
<div id="A1.p3" class="ltx_para ltx_noindent">
<svg id="A1.p3.pic1" class="ltx_picture" height="45341.08" overflow="visible" version="1.1" width="45341.08"><g transform="translate(0,45341.08) matrix(1 0 0 -1 0 0) translate(22670.54,0) translate(0,22670.54)" fill="#000000" stroke="#000000" stroke-width="0.4pt"><clipPath id="pgfcp14"><path d="M -22670.54 -22670.54 L 22670.54 -22670.54 L 22670.54 22670.54 L -22670.54 22670.54 Z M 0 5.91 L 0 412.11 C 0 415.37 2.64 418.02 5.91 418.02 L 594.09 418.02 C 597.36 418.02 600 415.37 600 412.11 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z"></path></clipPath><g fill-rule="evenodd"><g fill="#0000BF" fill-opacity="1.0"><path d="M 0 5.91 L 0 412.11 C 0 415.37 2.64 418.02 5.91 418.02 L 594.09 418.02 C 597.36 418.02 600 415.37 600 412.11 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z M 1.97 5.91 L 1.97 387.94 L 598.03 387.94 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill="#FFFFFF" fill-opacity="1.0"><path d="M 1.97 5.91 L 1.97 387.94 L 598.03 387.94 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 396.83)"><foreignObject width="568.39" height="12.3" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#FFFFFF">
<span id="A1.p3.pic1.1.1.1.1.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A1.p3.pic1.1.1.1.1.1.1.1" class="ltx_p"><span id="A1.p3.pic1.1.1.1.1.1.1.1.1" class="ltx_text ltx_font_bold ltx_font_italic">Meeting Planning</span></span>
</span></foreignObject></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 15.81)"><foreignObject width="568.39" height="358.3" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#000000">
<span id="A1.p3.pic1.2.2.2.2.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A1.p3.pic1.2.2.2.2.1.1.1" class="ltx_p"><span id="A1.p3.pic1.2.2.2.2.1.1.1.1" class="ltx_text ltx_font_bold">Prompt:</span></span>
<span id="A1.p3.pic1.2.2.2.2.1.1.2" class="ltx_p">You arrive at SOMA (South of Market) at 9:00AM. Joseph will be at Alamo Square from 4:15PM to 6:30PM. You’d like to meet Joseph for a minimum of 105 minutes. Andrew will be at Haight-Ashbury from 4:30PM to 6:15PM. You’d like to meet Andrew for a minimum of 30 minutes. John will be at Nob Hill from 7:15AM to 11:00AM. You’d like to meet John for a minimum of 75 minutes.</span>
<span id="A1.p3.pic1.2.2.2.2.1.1.3" class="ltx_p">It takes 27 minutes to travel between Sunset District and Nob Hill via car. It takes 18 minutes to travel between Sunset District and Alamo Square via car. It takes 11 minutes to travel between Sunset District and Golden Gate Park via car. It takes 25 minutes to travel between Nob Hill and Sunset District via car. It takes 11 minutes to travel between Nob Hill and Alamo Square via car. It takes 18 minutes to travel between Nob Hill and Golden Gate Park via car. It takes 16 minutes to travel between Alamo Square and Sunset District via car. It takes 11 minutes to travel between Alamo Square and Nob Hill via car. It takes 9 minutes to travel between Alamo Square and Golden Gate Park via car. It takes 10 minutes to travel between Golden Gate Park and Sunset District via car. It takes 19 minutes to travel between Golden Gate Park and Nob Hill via car. It takes 10 minutes to travel between Golden Gate Park and Alamo Square via car.</span>
<span id="A1.p3.pic1.2.2.2.2.1.1.4" class="ltx_p"><span id="A1.p3.pic1.2.2.2.2.1.1.4.1" class="ltx_text ltx_font_bold">Solution:</span></span>
<span id="A1.p3.pic1.2.2.2.2.1.1.5" class="ltx_p">You start at SOMA (South of Market) at 9:00AM. You travel to Nob Hill in 10 minutes and arrive at 9:10AM. You meet John for 75 minutes from 9:10AM to 10:25AM. You travel to Alamo Square in 11 minutes and arrive at 10:36AM. You wait until 4:15PM. You meet Joseph for 105 minutes from 4:15PM to 6:00PM.</span>
</span></foreignObject></g></g></g></svg>
</div>
<div id="A1.p4" class="ltx_para ltx_noindent">
<svg id="A1.p4.pic1" class="ltx_picture" height="45341.08" overflow="visible" version="1.1" width="45341.08"><g transform="translate(0,45341.08) matrix(1 0 0 -1 0 0) translate(22670.54,0) translate(0,22670.54)" fill="#000000" stroke="#000000" stroke-width="0.4pt"><clipPath id="pgfcp15"><path d="M -22670.54 -22670.54 L 22670.54 -22670.54 L 22670.54 22670.54 L -22670.54 22670.54 Z M 0 5.91 L 0 182.34 C 0 185.6 2.64 188.25 5.91 188.25 L 594.09 188.25 C 597.36 188.25 600 185.6 600 182.34 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z"></path></clipPath><g fill-rule="evenodd"><g fill="#0000BF" fill-opacity="1.0"><path d="M 0 5.91 L 0 182.34 C 0 185.6 2.64 188.25 5.91 188.25 L 594.09 188.25 C 597.36 188.25 600 185.6 600 182.34 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z M 1.97 5.91 L 1.97 158.17 L 598.03 158.17 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill="#FFFFFF" fill-opacity="1.0"><path d="M 1.97 5.91 L 1.97 158.17 L 598.03 158.17 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 167.06)"><foreignObject width="568.39" height="12.3" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#FFFFFF">
<span id="A1.p4.pic1.1.1.1.1.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A1.p4.pic1.1.1.1.1.1.1.1" class="ltx_p"><span id="A1.p4.pic1.1.1.1.1.1.1.1.1" class="ltx_text ltx_font_bold ltx_font_italic">Calendar Scheduling</span></span>
</span></foreignObject></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 15.81)"><foreignObject width="568.39" height="128.53" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#000000">
<span id="A1.p4.pic1.2.2.2.2.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A1.p4.pic1.2.2.2.2.1.1.1" class="ltx_p"><span id="A1.p4.pic1.2.2.2.2.1.1.1.1" class="ltx_text ltx_font_bold">Prompt:</span></span>
<span id="A1.p4.pic1.2.2.2.2.1.1.2" class="ltx_p">You need to schedule a meeting for Harold and Patrick for half an hour between the work hours of 9:00 to 17:00 on Monday.</span>
<span id="A1.p4.pic1.2.2.2.2.1.1.3" class="ltx_p">Harold’s calendar is wide open the entire day.
Patrick is busy on Monday during 9:00 to 9:30, 10:30 to 12:00, 12:30 to 13:30, 14:00 to 14:30, 15:00 to 16:30;</span>
<span id="A1.p4.pic1.2.2.2.2.1.1.4" class="ltx_p">Find a time that works for everyone’s schedule and constraints.</span>
<span id="A1.p4.pic1.2.2.2.2.1.1.5" class="ltx_p"><span id="A1.p4.pic1.2.2.2.2.1.1.5.1" class="ltx_text ltx_font_bold">Solution:</span></span>
<span id="A1.p4.pic1.2.2.2.2.1.1.6" class="ltx_p">Here is the proposed time: Monday, 9:30 - 10:00</span>
</span></foreignObject></g></g></g></svg>
</div>
</section>
<section id="A2" class="ltx_appendix">
<h2 class="ltx_title ltx_title_appendix">
<span class="ltx_tag ltx_tag_appendix">Appendix B </span>Prompts</h2>

<div id="A2.p1" class="ltx_para ltx_noindent">
<p id="A2.p1.1" class="ltx_p">Here is the 5-shot prompt for inference of <span id="A2.p1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span>. Similar prompts are used for <span id="A2.p1.1.2" class="ltx_text ltx_font_italic">Meeting Planning</span>, and <span id="A2.p1.1.3" class="ltx_text ltx_font_italic">Calendar Scheduling</span>.</p>
</div>
<div id="A2.p2" class="ltx_para ltx_noindent">
<svg id="A2.p2.pic1" class="ltx_picture" height="45341.08" overflow="visible" version="1.1" width="45341.08"><g transform="translate(0,45341.08) matrix(1 0 0 -1 0 0) translate(22670.54,0) translate(0,22670.54)" fill="#000000" stroke="#000000" stroke-width="0.4pt"><clipPath id="pgfcp16"><path d="M -22670.54 -22670.54 L 22670.54 -22670.54 L 22670.54 22670.54 L -22670.54 22670.54 Z M 0 5.91 L 0 212.71 C 0 215.97 2.64 218.61 5.91 218.61 L 594.09 218.61 C 597.36 218.61 600 215.97 600 212.71 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z"></path></clipPath><g fill-rule="evenodd"><g fill="#0000BF" fill-opacity="1.0"><path d="M 0 5.91 L 0 212.71 C 0 215.97 2.64 218.61 5.91 218.61 L 594.09 218.61 C 597.36 218.61 600 215.97 600 212.71 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z M 1.97 5.91 L 1.97 188.54 L 598.03 188.54 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill="#FFFFFF" fill-opacity="1.0"><path d="M 1.97 5.91 L 1.97 188.54 L 598.03 188.54 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 197.42)"><foreignObject width="568.39" height="12.3" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#FFFFFF">
<span id="A2.p2.pic1.11.11.11.11.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A2.p2.pic1.11.11.11.11.1.1.1" class="ltx_p"><span id="A2.p2.pic1.11.11.11.11.1.1.1.1" class="ltx_text ltx_font_bold">Standard 5-Shot Prompt for <span id="A2.p2.pic1.11.11.11.11.1.1.1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span></span></span>
</span></foreignObject></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 15.81)"><foreignObject width="568.39" height="158.89" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#000000">
<span id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.11" class="ltx_p"><span id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.11.1" class="ltx_text ltx_font_bold">Prompt:</span></span>
<span id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.12" class="ltx_p">You are an expert at planning trips. You are given a few constraints regarding the cities to visit and the durations of staying at each city. You are also given the flight information between the cities. Here are a few example tasks and solutions:</span>
<span id="A2.p2.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2" class="ltx_p">TASK: <math id="A2.p2.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1" class="ltx_Math" alttext="&lt;" display="inline"><semantics id="A2.p2.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1a"><mo id="A2.p2.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1.1" xref="A2.p2.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1.1.cmml">&lt;</mo><annotation-xml encoding="MathML-Content" id="A2.p2.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1b"><lt id="A2.p2.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1.1.cmml" xref="A2.p2.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1.1"></lt></annotation-xml><annotation encoding="application/x-tex" id="A2.p2.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1c">&lt;</annotation></semantics></math>task1<math id="A2.p2.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1" class="ltx_Math" alttext="&gt;" display="inline"><semantics id="A2.p2.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1a"><mo id="A2.p2.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1.1" xref="A2.p2.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1.1.cmml">&gt;</mo><annotation-xml encoding="MathML-Content" id="A2.p2.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1b"><gt id="A2.p2.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1.1.cmml" xref="A2.p2.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1.1"></gt></annotation-xml><annotation encoding="application/x-tex" id="A2.p2.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1c">&gt;</annotation></semantics></math></span>
<span id="A2.p2.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4" class="ltx_p">SOLUTION: <math id="A2.p2.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1" class="ltx_Math" alttext="&lt;" display="inline"><semantics id="A2.p2.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1a"><mo id="A2.p2.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1.1" xref="A2.p2.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1.1.cmml">&lt;</mo><annotation-xml encoding="MathML-Content" id="A2.p2.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1b"><lt id="A2.p2.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1.1.cmml" xref="A2.p2.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1.1"></lt></annotation-xml><annotation encoding="application/x-tex" id="A2.p2.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1c">&lt;</annotation></semantics></math>solution1<math id="A2.p2.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1" class="ltx_Math" alttext="&gt;" display="inline"><semantics id="A2.p2.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1a"><mo id="A2.p2.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1.1" xref="A2.p2.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1.1.cmml">&gt;</mo><annotation-xml encoding="MathML-Content" id="A2.p2.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1b"><gt id="A2.p2.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1.1.cmml" xref="A2.p2.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1.1"></gt></annotation-xml><annotation encoding="application/x-tex" id="A2.p2.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1c">&gt;</annotation></semantics></math></span>
<span id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.13" class="ltx_p">…</span>
<span id="A2.p2.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6" class="ltx_p">TASK: <math id="A2.p2.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1" class="ltx_Math" alttext="&lt;" display="inline"><semantics id="A2.p2.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1a"><mo id="A2.p2.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1.1" xref="A2.p2.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1.1.cmml">&lt;</mo><annotation-xml encoding="MathML-Content" id="A2.p2.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1b"><lt id="A2.p2.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1.1.cmml" xref="A2.p2.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1.1"></lt></annotation-xml><annotation encoding="application/x-tex" id="A2.p2.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1c">&lt;</annotation></semantics></math>task5<math id="A2.p2.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1" class="ltx_Math" alttext="&gt;" display="inline"><semantics id="A2.p2.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1a"><mo id="A2.p2.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1.1" xref="A2.p2.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1.1.cmml">&gt;</mo><annotation-xml encoding="MathML-Content" id="A2.p2.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1b"><gt id="A2.p2.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1.1.cmml" xref="A2.p2.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1.1"></gt></annotation-xml><annotation encoding="application/x-tex" id="A2.p2.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1c">&gt;</annotation></semantics></math></span>
<span id="A2.p2.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8" class="ltx_p">SOLUTION: <math id="A2.p2.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1" class="ltx_Math" alttext="&lt;" display="inline"><semantics id="A2.p2.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1a"><mo id="A2.p2.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1.1" xref="A2.p2.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1.1.cmml">&lt;</mo><annotation-xml encoding="MathML-Content" id="A2.p2.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1b"><lt id="A2.p2.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1.1.cmml" xref="A2.p2.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1.1"></lt></annotation-xml><annotation encoding="application/x-tex" id="A2.p2.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1c">&lt;</annotation></semantics></math>solution5<math id="A2.p2.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1" class="ltx_Math" alttext="&gt;" display="inline"><semantics id="A2.p2.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1a"><mo id="A2.p2.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1.1" xref="A2.p2.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1.1.cmml">&gt;</mo><annotation-xml encoding="MathML-Content" id="A2.p2.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1b"><gt id="A2.p2.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1.1.cmml" xref="A2.p2.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1.1"></gt></annotation-xml><annotation encoding="application/x-tex" id="A2.p2.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1c">&gt;</annotation></semantics></math></span>
<span id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10" class="ltx_p">TASK: <math id="A2.p2.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1" class="ltx_Math" alttext="&lt;" display="inline"><semantics id="A2.p2.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1a"><mo id="A2.p2.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1.1" xref="A2.p2.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1.1.cmml">&lt;</mo><annotation-xml encoding="MathML-Content" id="A2.p2.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1b"><lt id="A2.p2.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1.1.cmml" xref="A2.p2.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1.1"></lt></annotation-xml><annotation encoding="application/x-tex" id="A2.p2.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1c">&lt;</annotation></semantics></math>task<math id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1" class="ltx_Math" alttext="&gt;" display="inline"><semantics id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1a"><mo id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1.1" xref="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1.1.cmml">&gt;</mo><annotation-xml encoding="MathML-Content" id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1b"><gt id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1.1.cmml" xref="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1.1"></gt></annotation-xml><annotation encoding="application/x-tex" id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1c">&gt;</annotation></semantics></math></span>
<span id="A2.p2.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.14" class="ltx_p">SOLUTION:</span>
</span></foreignObject></g></g></g></svg>
</div>
<div id="A2.p3" class="ltx_para ltx_noindent">
<p id="A2.p3.1" class="ltx_p">Here is the prompt used for easy-to-hard and hard-to-easy generalization ablations of <span id="A2.p3.1.1" class="ltx_text ltx_font_italic">Trip Planning</span>:</p>
</div>
<div id="A2.p4" class="ltx_para ltx_noindent">
<svg id="A2.p4.pic1" class="ltx_picture" height="45341.08" overflow="visible" version="1.1" width="45341.08"><g transform="translate(0,45341.08) matrix(1 0 0 -1 0 0) translate(22670.54,0) translate(0,22670.54)" fill="#000000" stroke="#000000" stroke-width="0.4pt"><clipPath id="pgfcp17"><path d="M -22670.54 -22670.54 L 22670.54 -22670.54 L 22670.54 22670.54 L -22670.54 22670.54 Z M 0 5.91 L 0 214.24 C 0 217.5 2.64 220.15 5.91 220.15 L 594.09 220.15 C 597.36 220.15 600 217.5 600 214.24 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z"></path></clipPath><g fill-rule="evenodd"><g fill="#0000BF" fill-opacity="1.0"><path d="M 0 5.91 L 0 214.24 C 0 217.5 2.64 220.15 5.91 220.15 L 594.09 220.15 C 597.36 220.15 600 217.5 600 214.24 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z M 1.97 5.91 L 1.97 188.54 L 598.03 188.54 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill="#FFFFFF" fill-opacity="1.0"><path d="M 1.97 5.91 L 1.97 188.54 L 598.03 188.54 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 197.42)"><foreignObject width="568.39" height="13.84" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#FFFFFF">
<span id="A2.p4.pic1.11.11.11.11.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A2.p4.pic1.11.11.11.11.1.1.1" class="ltx_p"><span id="A2.p4.pic1.11.11.11.11.1.1.1.1" class="ltx_text ltx_font_bold">Easy-to-Hard/Hard-to-Easy Prompt for <span id="A2.p4.pic1.11.11.11.11.1.1.1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span></span></span>
</span></foreignObject></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 15.81)"><foreignObject width="568.39" height="158.89" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#000000">
<span id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.11" class="ltx_p"><span id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.11.1" class="ltx_text ltx_font_bold">Prompt:</span></span>
<span id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.12" class="ltx_p">You are an expert at planning trips. You are given a few constraints regarding the cities to visit and the durations of staying at each city. You are also given the flight information between the cities. Here are a few example tasks and solutions:</span>
<span id="A2.p4.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2" class="ltx_p">TASK: <math id="A2.p4.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1" class="ltx_Math" alttext="&lt;" display="inline"><semantics id="A2.p4.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1a"><mo id="A2.p4.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1.1" xref="A2.p4.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1.1.cmml">&lt;</mo><annotation-xml encoding="MathML-Content" id="A2.p4.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1b"><lt id="A2.p4.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1.1.cmml" xref="A2.p4.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1.1"></lt></annotation-xml><annotation encoding="application/x-tex" id="A2.p4.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1c">&lt;</annotation></semantics></math>easy/hard task1<math id="A2.p4.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1" class="ltx_Math" alttext="&gt;" display="inline"><semantics id="A2.p4.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1a"><mo id="A2.p4.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1.1" xref="A2.p4.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1.1.cmml">&gt;</mo><annotation-xml encoding="MathML-Content" id="A2.p4.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1b"><gt id="A2.p4.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1.1.cmml" xref="A2.p4.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1.1"></gt></annotation-xml><annotation encoding="application/x-tex" id="A2.p4.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1c">&gt;</annotation></semantics></math></span>
<span id="A2.p4.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4" class="ltx_p">SOLUTION: <math id="A2.p4.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1" class="ltx_Math" alttext="&lt;" display="inline"><semantics id="A2.p4.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1a"><mo id="A2.p4.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1.1" xref="A2.p4.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1.1.cmml">&lt;</mo><annotation-xml encoding="MathML-Content" id="A2.p4.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1b"><lt id="A2.p4.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1.1.cmml" xref="A2.p4.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1.1"></lt></annotation-xml><annotation encoding="application/x-tex" id="A2.p4.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1c">&lt;</annotation></semantics></math>solution1<math id="A2.p4.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1" class="ltx_Math" alttext="&gt;" display="inline"><semantics id="A2.p4.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1a"><mo id="A2.p4.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1.1" xref="A2.p4.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1.1.cmml">&gt;</mo><annotation-xml encoding="MathML-Content" id="A2.p4.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1b"><gt id="A2.p4.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1.1.cmml" xref="A2.p4.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1.1"></gt></annotation-xml><annotation encoding="application/x-tex" id="A2.p4.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1c">&gt;</annotation></semantics></math></span>
<span id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.13" class="ltx_p">…</span>
<span id="A2.p4.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6" class="ltx_p">TASK: <math id="A2.p4.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1" class="ltx_Math" alttext="&lt;" display="inline"><semantics id="A2.p4.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1a"><mo id="A2.p4.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1.1" xref="A2.p4.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1.1.cmml">&lt;</mo><annotation-xml encoding="MathML-Content" id="A2.p4.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1b"><lt id="A2.p4.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1.1.cmml" xref="A2.p4.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1.1"></lt></annotation-xml><annotation encoding="application/x-tex" id="A2.p4.pic1.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.m1.1c">&lt;</annotation></semantics></math>easy/hard task5<math id="A2.p4.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1" class="ltx_Math" alttext="&gt;" display="inline"><semantics id="A2.p4.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1a"><mo id="A2.p4.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1.1" xref="A2.p4.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1.1.cmml">&gt;</mo><annotation-xml encoding="MathML-Content" id="A2.p4.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1b"><gt id="A2.p4.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1.1.cmml" xref="A2.p4.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1.1"></gt></annotation-xml><annotation encoding="application/x-tex" id="A2.p4.pic1.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.m2.1c">&gt;</annotation></semantics></math></span>
<span id="A2.p4.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8" class="ltx_p">SOLUTION: <math id="A2.p4.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1" class="ltx_Math" alttext="&lt;" display="inline"><semantics id="A2.p4.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1a"><mo id="A2.p4.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1.1" xref="A2.p4.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1.1.cmml">&lt;</mo><annotation-xml encoding="MathML-Content" id="A2.p4.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1b"><lt id="A2.p4.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1.1.cmml" xref="A2.p4.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1.1"></lt></annotation-xml><annotation encoding="application/x-tex" id="A2.p4.pic1.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.m1.1c">&lt;</annotation></semantics></math>solution5<math id="A2.p4.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1" class="ltx_Math" alttext="&gt;" display="inline"><semantics id="A2.p4.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1a"><mo id="A2.p4.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1.1" xref="A2.p4.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1.1.cmml">&gt;</mo><annotation-xml encoding="MathML-Content" id="A2.p4.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1b"><gt id="A2.p4.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1.1.cmml" xref="A2.p4.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1.1"></gt></annotation-xml><annotation encoding="application/x-tex" id="A2.p4.pic1.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.m2.1c">&gt;</annotation></semantics></math></span>
<span id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10" class="ltx_p">TASK: <math id="A2.p4.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1" class="ltx_Math" alttext="&lt;" display="inline"><semantics id="A2.p4.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1a"><mo id="A2.p4.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1.1" xref="A2.p4.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1.1.cmml">&lt;</mo><annotation-xml encoding="MathML-Content" id="A2.p4.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1b"><lt id="A2.p4.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1.1.cmml" xref="A2.p4.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1.1"></lt></annotation-xml><annotation encoding="application/x-tex" id="A2.p4.pic1.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.m1.1c">&lt;</annotation></semantics></math>task<math id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1" class="ltx_Math" alttext="&gt;" display="inline"><semantics id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1a"><mo id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1.1" xref="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1.1.cmml">&gt;</mo><annotation-xml encoding="MathML-Content" id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1b"><gt id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1.1.cmml" xref="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1.1"></gt></annotation-xml><annotation encoding="application/x-tex" id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.m2.1c">&gt;</annotation></semantics></math></span>
<span id="A2.p4.pic1.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.10.14" class="ltx_p">SOLUTION:</span>
</span></foreignObject></g></g></g></svg>
</div>
<div id="A2.p5" class="ltx_para ltx_noindent">
<p id="A2.p5.1" class="ltx_p">Here is the self-correction prompt used for <span id="A2.p5.1.1" class="ltx_text ltx_font_italic">Trip Planning</span> self-correction ablation:
<br class="ltx_break"></p>
</div>
<div id="A2.p6" class="ltx_para ltx_noindent">
<svg id="A2.p6.pic1" class="ltx_picture" height="45341.08" overflow="visible" version="1.1" width="45341.08"><g transform="translate(0,45341.08) matrix(1 0 0 -1 0 0) translate(22670.54,0) translate(0,22670.54)" fill="#000000" stroke="#000000" stroke-width="0.4pt"><clipPath id="pgfcp18"><path d="M -22670.54 -22670.54 L 22670.54 -22670.54 L 22670.54 22670.54 L -22670.54 22670.54 Z M 0 5.91 L 0 213.63 C 0 216.89 2.64 219.53 5.91 219.53 L 594.09 219.53 C 597.36 219.53 600 216.89 600 213.63 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z"></path></clipPath><g fill-rule="evenodd"><g fill="#0000BF" fill-opacity="1.0"><path d="M 0 5.91 L 0 213.63 C 0 216.89 2.64 219.53 5.91 219.53 L 594.09 219.53 C 597.36 219.53 600 216.89 600 213.63 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z M 1.97 5.91 L 1.97 189.46 L 598.03 189.46 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill="#FFFFFF" fill-opacity="1.0"><path d="M 1.97 5.91 L 1.97 189.46 L 598.03 189.46 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 198.35)"><foreignObject width="568.39" height="12.3" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#FFFFFF">
<span id="A2.p6.pic1.5.5.5.5.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A2.p6.pic1.5.5.5.5.1.1.1" class="ltx_p"><span id="A2.p6.pic1.5.5.5.5.1.1.1.1" class="ltx_text ltx_font_bold">Self-Correction Prompt for <span id="A2.p6.pic1.5.5.5.5.1.1.1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span></span></span>
</span></foreignObject></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 15.81)"><foreignObject width="568.39" height="159.82" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#000000">
<span id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.5" class="ltx_p"><span id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.5.1" class="ltx_text ltx_font_bold">Prompt:</span></span>
<span id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.6" class="ltx_p">You are an expert at planning trips. You are given a TASK of Trip Planning request, and a proposed SOLUTION. Your job is to identify any error in the SOLUTION, correct the error and generate a new solution. If there is no error, simple output the proposed SOLUTION.</span>
<span id="A2.p6.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2" class="ltx_p">TASK: <math id="A2.p6.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1" class="ltx_Math" alttext="&lt;" display="inline"><semantics id="A2.p6.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1a"><mo id="A2.p6.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1.1" xref="A2.p6.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1.1.cmml">&lt;</mo><annotation-xml encoding="MathML-Content" id="A2.p6.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1b"><lt id="A2.p6.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1.1.cmml" xref="A2.p6.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1.1"></lt></annotation-xml><annotation encoding="application/x-tex" id="A2.p6.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.m1.1c">&lt;</annotation></semantics></math>task<math id="A2.p6.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1" class="ltx_Math" alttext="&gt;" display="inline"><semantics id="A2.p6.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1a"><mo id="A2.p6.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1.1" xref="A2.p6.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1.1.cmml">&gt;</mo><annotation-xml encoding="MathML-Content" id="A2.p6.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1b"><gt id="A2.p6.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1.1.cmml" xref="A2.p6.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1.1"></gt></annotation-xml><annotation encoding="application/x-tex" id="A2.p6.pic1.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.m2.1c">&gt;</annotation></semantics></math></span>
<span id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4" class="ltx_p">SOLUTION: <math id="A2.p6.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1" class="ltx_Math" alttext="&lt;" display="inline"><semantics id="A2.p6.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1a"><mo id="A2.p6.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1.1" xref="A2.p6.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1.1.cmml">&lt;</mo><annotation-xml encoding="MathML-Content" id="A2.p6.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1b"><lt id="A2.p6.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1.1.cmml" xref="A2.p6.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1.1"></lt></annotation-xml><annotation encoding="application/x-tex" id="A2.p6.pic1.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.m1.1c">&lt;</annotation></semantics></math>model output<math id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1" class="ltx_Math" alttext="&gt;" display="inline"><semantics id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1a"><mo id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1.1" xref="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1.1.cmml">&gt;</mo><annotation-xml encoding="MathML-Content" id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1b"><gt id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1.1.cmml" xref="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1.1"></gt></annotation-xml><annotation encoding="application/x-tex" id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.m2.1c">&gt;</annotation></semantics></math></span>
<span id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.7" class="ltx_p">Please self correct the solution if there is any error and output your solution in the following format and keep the NEW SOLUTION in the same format as SOLUTION:</span>
<span id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.8" class="ltx_p">**ERROR IDENTIFIED:**</span>
<span id="A2.p6.pic1.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.9" class="ltx_p">**NEW SOLUTION:**</span>
</span></foreignObject></g></g></g></svg>
</div>
</section>
<section id="A3" class="ltx_appendix">
<h2 class="ltx_title ltx_title_appendix">
<span class="ltx_tag ltx_tag_appendix">Appendix C </span>Plan Parsing and Scoring</h2>

<div id="A3.p1" class="ltx_para ltx_noindent">
<p id="A3.p1.1" class="ltx_p">In this section, we describe the details on how to parse the plans generated by models, and score the exact-match score against the ground-truth plans. We rely on the few-shot exemplars to make sure the generated plans from models follow the same template solutions provided in few-shot examples. Then, we rely on regex expressions to extract the exact date/place/time information to compare against the ground-truth plans. For example, in <span id="A3.p1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span>, we use a regex expression <span id="A3.p1.1.2" class="ltx_text ltx_font_italic">r".*Day (\d+).*from (\w+) to (\w+)"</span> to parse the date D of flight from city X to Y. We do similar regex parsing to the other two tasks. For exact match score, only if all the information (e.g. D, X and Y) matches, we score the plan to be correct.</p>
</div>
</section>
<section id="A4" class="ltx_appendix">
<h2 class="ltx_title ltx_title_appendix">
<span class="ltx_tag ltx_tag_appendix">Appendix D </span>Analysis of GPT-4o on <span id="A4.1.1" class="ltx_text ltx_font_italic">Trip Planning</span>
</h2>

<div id="A4.p1" class="ltx_para ltx_noindent">
<p id="A4.p1.1" class="ltx_p">We sample 10 examples where GPT-4o made an error on <span id="A4.p1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span>, and annotate the type of errors GPT-4o made. All of the errors are due to the fact that GPT-4o failed to understand and respect the constraints in the task. 7/10 are failures in respecting the Flight Connectivity constraints while the other 3/10 are due to Travel Date constraint failures. Below shows an example for both cases.</p>
</div>
<div id="A4.p2" class="ltx_para ltx_noindent">
<svg id="A4.p2.pic1" class="ltx_picture" height="45341.08" overflow="visible" version="1.1" width="45341.08"><g transform="translate(0,45341.08) matrix(1 0 0 -1 0 0) translate(22670.54,0) translate(0,22670.54)" fill="#000000" stroke="#000000" stroke-width="0.4pt"><clipPath id="pgfcp19"><path d="M -22670.54 -22670.54 L 22670.54 -22670.54 L 22670.54 22670.54 L -22670.54 22670.54 Z M 0 5.91 L 0 419.11 C 0 422.37 2.64 425.01 5.91 425.01 L 594.09 425.01 C 597.36 425.01 600 422.37 600 419.11 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z"></path></clipPath><g fill-rule="evenodd"><g fill="#0000BF" fill-opacity="1.0"><path d="M 0 5.91 L 0 419.11 C 0 422.37 2.64 425.01 5.91 425.01 L 594.09 425.01 C 597.36 425.01 600 422.37 600 419.11 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z M 1.97 5.91 L 1.97 394.94 L 598.03 394.94 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill="#FFFFFF" fill-opacity="1.0"><path d="M 1.97 5.91 L 1.97 394.94 L 598.03 394.94 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 403.83)"><foreignObject width="568.39" height="12.3" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#FFFFFF">
<span id="A4.p2.pic1.1.1.1.1.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A4.p2.pic1.1.1.1.1.1.1.1" class="ltx_p"><span id="A4.p2.pic1.1.1.1.1.1.1.1.1" class="ltx_text ltx_font_bold">GPT-4o Error on <span id="A4.p2.pic1.1.1.1.1.1.1.1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span>: Flight Connectivity</span></span>
</span></foreignObject></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 15.81)"><foreignObject width="568.39" height="365.3" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#000000">
<span id="A4.p2.pic1.2.2.2.2.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A4.p2.pic1.2.2.2.2.1.1.1" class="ltx_p"><span id="A4.p2.pic1.2.2.2.2.1.1.1.1" class="ltx_text ltx_font_bold">Task:</span></span>
<span id="A4.p2.pic1.2.2.2.2.1.1.2" class="ltx_p">You plan to visit 3 European cities for 14 days in total. You only take direct flights to commute between cities. You would like to visit Florence for 6 days. You want to meet a friend in Florence between day 9 and day 14. You would like to visit Barcelona for 5 days. You would like to visit Helsinki for 5 days.</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.3" class="ltx_p">Here are the cities that have direct flights:
Barcelona and Florence, Helsinki and Barcelona.</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.4" class="ltx_p">Find a trip plan of visiting the cities for 14 days by taking direct flights to commute between them.</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.5" class="ltx_p"><span id="A4.p2.pic1.2.2.2.2.1.1.5.1" class="ltx_text ltx_font_bold">Solution:</span></span>
<span id="A4.p2.pic1.2.2.2.2.1.1.6" class="ltx_p">Here is the trip plan for visiting the 3 European cities for 14 days:</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.7" class="ltx_p">**Day 1-5:** Arriving in Helsinki and visit Helsinki for 5 days.</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.8" class="ltx_p">**Day 5:** Fly from Helsinki to Barcelona.</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.9" class="ltx_p">**Day 5-9:** Visit Barcelona for 5 days.</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.10" class="ltx_p">**Day 9:** Fly from Barcelona to Florence.</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.11" class="ltx_p">**Day 9-14:** Visit Florence for 6 days.</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.12" class="ltx_p"><span id="A4.p2.pic1.2.2.2.2.1.1.12.1" class="ltx_text ltx_font_bold">GPT-4o Output:</span></span>
<span id="A4.p2.pic1.2.2.2.2.1.1.13" class="ltx_p">"Here is the trip plan for visiting the 3 European cities for 14 days:</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.14" class="ltx_p">**Day 1-5:** Arriving in Barcelona and visit Barcelona for 5 days.</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.15" class="ltx_p">**Day 5:** Fly from Barcelona to Helsinki.</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.16" class="ltx_p">**Day 5-10:** Visit Helsinki for 5 days.</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.17" class="ltx_p">**Day 10:** Fly from Helsinki to Florence.</span>
<span id="A4.p2.pic1.2.2.2.2.1.1.18" class="ltx_p">**Day 10-14:** Visit Florence for 6 days.</span>
</span></foreignObject></g></g></g></svg>
</div>
<div id="A4.p3" class="ltx_para ltx_noindent">
<svg id="A4.p3.pic1" class="ltx_picture" height="45341.08" overflow="visible" version="1.1" width="45341.08"><g transform="translate(0,45341.08) matrix(1 0 0 -1 0 0) translate(22670.54,0) translate(0,22670.54)" fill="#000000" stroke="#000000" stroke-width="0.4pt"><clipPath id="pgfcp20"><path d="M -22670.54 -22670.54 L 22670.54 -22670.54 L 22670.54 22670.54 L -22670.54 22670.54 Z M 0 5.91 L 0 398.97 C 0 402.23 2.64 404.87 5.91 404.87 L 594.09 404.87 C 597.36 404.87 600 402.23 600 398.97 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z"></path></clipPath><g fill-rule="evenodd"><g fill="#0000BF" fill-opacity="1.0"><path d="M 0 5.91 L 0 398.97 C 0 402.23 2.64 404.87 5.91 404.87 L 594.09 404.87 C 597.36 404.87 600 402.23 600 398.97 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z M 1.97 5.91 L 1.97 374.8 L 598.03 374.8 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill="#FFFFFF" fill-opacity="1.0"><path d="M 1.97 5.91 L 1.97 374.8 L 598.03 374.8 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 383.69)"><foreignObject width="568.39" height="12.3" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#FFFFFF">
<span id="A4.p3.pic1.1.1.1.1.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A4.p3.pic1.1.1.1.1.1.1.1" class="ltx_p"><span id="A4.p3.pic1.1.1.1.1.1.1.1.1" class="ltx_text ltx_font_bold">GPT-4o Error on <span id="A4.p3.pic1.1.1.1.1.1.1.1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span>: Travel Date</span></span>
</span></foreignObject></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 15.81)"><foreignObject width="568.39" height="345.16" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#000000">
<span id="A4.p3.pic1.2.2.2.2.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A4.p3.pic1.2.2.2.2.1.1.1" class="ltx_p"><span id="A4.p3.pic1.2.2.2.2.1.1.1.1" class="ltx_text ltx_font_bold">Task:</span></span>
<span id="A4.p3.pic1.2.2.2.2.1.1.2" class="ltx_p">You plan to visit 3 European cities for 8 days in total. You only take direct flights to commute between cities. You would like to visit Dubrovnik for 3 days. You would like to visit Berlin for 4 days. During day 1 and day 4, you have to attend a conference in Berlin. You would like to visit Munich for 3 days.</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.3" class="ltx_p">Here are the cities that have direct flights:
Munich and Dubrovnik, Berlin and Munich.</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.4" class="ltx_p">Find a trip plan of visiting the cities for 8 days by taking direct flights to commute between them.</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.5" class="ltx_p"><span id="A4.p3.pic1.2.2.2.2.1.1.5.1" class="ltx_text ltx_font_bold">Solution:</span></span>
<span id="A4.p3.pic1.2.2.2.2.1.1.6" class="ltx_p">"Here is the trip plan for visiting the 3 European cities for 8 days:</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.7" class="ltx_p">**Day 1-4:** Arriving in Berlin and visit Berlin for 4 days.</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.8" class="ltx_p">**Day 4:** Fly from Berlin to Munich.</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.9" class="ltx_p">**Day 4-6:** Visit Munich for 3 days.</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.10" class="ltx_p">**Day 6:** Fly from Munich to Dubrovnik.</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.11" class="ltx_p">**Day 6-8:** Visit Dubrovnik for 3 days."</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.12" class="ltx_p"><span id="A4.p3.pic1.2.2.2.2.1.1.12.1" class="ltx_text ltx_font_bold">GPT-4o Output:</span></span>
<span id="A4.p3.pic1.2.2.2.2.1.1.13" class="ltx_p">"ere is the trip plan for visiting the 3 European cities for 8 days:</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.14" class="ltx_p">**Day 1-4:** Arriving in Berlin and attend the conference while visiting Berlin for 4 days.
**Day 4:** Fly from Berlin to Munich.</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.15" class="ltx_p">**Day 4-7:** Visit Munich for 3 days.</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.16" class="ltx_p">**Day 7:** Fly from Munich to Dubrovnik.</span>
<span id="A4.p3.pic1.2.2.2.2.1.1.17" class="ltx_p">**Day 7-10:** Visit Dubrovnik for 3 days.</span>
</span></foreignObject></g></g></g></svg>
</div>
</section>
<section id="A5" class="ltx_appendix">
<h2 class="ltx_title ltx_title_appendix">
<span class="ltx_tag ltx_tag_appendix">Appendix E </span>Self-Correction Example</h2>

<div id="A5.p1" class="ltx_para ltx_noindent">
<p id="A5.p1.1" class="ltx_p">Here we show an example of self-correction on <span id="A5.p1.1.1" class="ltx_text ltx_font_italic">Trip Planning</span>, to illustrate the model behavior after self-correction. The errors made by the models are highlighted in red.
<br class="ltx_break"></p>
</div>
<div id="A5.p2" class="ltx_para ltx_noindent">
<svg id="A5.p2.pic1" class="ltx_picture" height="45341.08" overflow="visible" version="1.1" width="45341.08"><g transform="translate(0,45341.08) matrix(1 0 0 -1 0 0) translate(22670.54,0) translate(0,22670.54)" fill="#000000" stroke="#000000" stroke-width="0.4pt"><clipPath id="pgfcp21"><path d="M -22670.54 -22670.54 L 22670.54 -22670.54 L 22670.54 22670.54 L -22670.54 22670.54 Z M 0 5.91 L 0 847.29 C 0 850.55 2.64 853.19 5.91 853.19 L 594.09 853.19 C 597.36 853.19 600 850.55 600 847.29 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z"></path></clipPath><g fill-rule="evenodd"><g fill="#0000BF" fill-opacity="1.0"><path d="M 0 5.91 L 0 847.29 C 0 850.55 2.64 853.19 5.91 853.19 L 594.09 853.19 C 597.36 853.19 600 850.55 600 847.29 L 600 5.91 C 600 2.64 597.36 0 594.09 0 L 5.91 0 C 2.64 0 0 2.64 0 5.91 Z M 1.97 5.91 L 1.97 823.12 L 598.03 823.12 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill="#FFFFFF" fill-opacity="1.0"><path d="M 1.97 5.91 L 1.97 823.12 L 598.03 823.12 L 598.03 5.91 C 598.03 3.73 596.27 1.97 594.09 1.97 L 5.91 1.97 C 3.73 1.97 1.97 3.73 1.97 5.91 Z" style="stroke:none"></path></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 832)"><foreignObject width="568.39" height="12.3" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#FFFFFF">
<span id="A5.p2.pic1.1.1.1.1.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A5.p2.pic1.1.1.1.1.1.1.1" class="ltx_p"><span id="A5.p2.pic1.1.1.1.1.1.1.1.1" class="ltx_text ltx_font_bold">Self-Correction Example</span></span>
</span></foreignObject></g><g fill-opacity="1.0" transform="matrix(1.0 0.0 0.0 1.0 15.81 15.81)"><foreignObject width="568.39" height="793.48" transform="matrix(1 0 0 -1 0 16.6)" overflow="visible" color="#000000">
<span id="A5.p2.pic1.2.2.2.2.1.1" class="ltx_inline-block ltx_minipage ltx_align_bottom" style="width:410.8pt;">
<span id="A5.p2.pic1.2.2.2.2.1.1.1" class="ltx_p"><span id="A5.p2.pic1.2.2.2.2.1.1.1.1" class="ltx_text ltx_font_bold">Task:</span></span>
<span id="A5.p2.pic1.2.2.2.2.1.1.2" class="ltx_p">You plan to visit 3 European cities for 14 days in total. You only take direct flights to commute between cities. You would like to visit Florence for 6 days. You want to meet a friend in Florence between day 9 and day 14. You would like to visit Barcelona for 5 days. You would like to visit Helsinki for 5 days.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.3" class="ltx_p">Here are the cities that have direct flights: Barcelona and Florence, Helsinki and Barcelona.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.4" class="ltx_p">Find a trip plan of visiting the cities for 14 days by taking direct flights to commute between them.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.5" class="ltx_p"><span id="A5.p2.pic1.2.2.2.2.1.1.5.1" class="ltx_text ltx_font_bold">Solution:</span></span>
<span id="A5.p2.pic1.2.2.2.2.1.1.6" class="ltx_p">Here is the trip plan for visiting the 3 European cities for 14 days:</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.7" class="ltx_p">**Day 1-5:** Arriving in Helsinki and visit Helsinki for 5 days.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.8" class="ltx_p">**Day 5:** Fly from Helsinki to Barcelona.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.9" class="ltx_p">**Day 5-9:** Visit Barcelona for 5 days.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.10" class="ltx_p">**Day 9:** Fly from Barcelona to Florence.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.11" class="ltx_p">**Day 9-14:** Visit Florence for 6 days.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.12" class="ltx_p"><span id="A5.p2.pic1.2.2.2.2.1.1.12.1" class="ltx_text ltx_font_bold">GPT-3.5 Output:</span></span>
<span id="A5.p2.pic1.2.2.2.2.1.1.13" class="ltx_p">**ERROR IDENTIFIED:** The error in the solution is that the friend’s visit in Florence is scheduled between day 10 and day 14, instead of between day 9 and day 14 as requested.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.14" class="ltx_p">**NEW SOLUTION:** Here is the corrected trip plan for visiting the 3 European cities for 14 days:</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.15" class="ltx_p">**Day 1-5:** Arriving in Helsinki and visit Helsinki for 5 days.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.16" class="ltx_p">**Day 5:** Fly from Helsinki to Barcelona.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.17" class="ltx_p">**Day 5-10:** Visit Barcelona for 5 days.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.18" class="ltx_p">**Day 10:** Fly from Barcelona to Florence.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.19" class="ltx_p">**Day 10-15:** Visit Florence for 6 days.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.20" class="ltx_p"><span id="A5.p2.pic1.2.2.2.2.1.1.20.1" class="ltx_text ltx_font_bold">GPT-4 Output:</span></span>
<span id="A5.p2.pic1.2.2.2.2.1.1.21" class="ltx_p">**ERROR IDENTIFIED:** The proposed solution has an error in the total number of days spent. The total number of days spent in the proposed solution is 15 days (5 days in Helsinki, 5 days in Barcelona, and 6 days in Florence), which is more than the 14 days available for the trip.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.22" class="ltx_p">**NEW SOLUTION:** Here is the corrected trip plan for visiting the 3 European cities for 14 days:</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.23" class="ltx_p">**Day 1-4:** Arriving in Helsinki and visit Helsinki for 4 days.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.24" class="ltx_p">**Day 5:** Fly from Helsinki to Barcelona.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.25" class="ltx_p">**Day 5-9:** Visit Barcelona for 5 days.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.26" class="ltx_p">**Day 10:** Fly from Barcelona to Florence.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.27" class="ltx_p">**Day 10-14:** Visit Florence for 5 days.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.28" class="ltx_p"><span id="A5.p2.pic1.2.2.2.2.1.1.28.1" class="ltx_text ltx_font_bold">Gemini Pro 1.5 Output:</span></span>
<span id="A5.p2.pic1.2.2.2.2.1.1.29" class="ltx_p">"**ERROR IDENTIFIED:** The proposed solution has overlapping days. For example, Day 5 is used for both visiting Helsinki and flying to Barcelona. Additionally, the solution doesn’t account for the fact that there are no direct flights between Helsinki and Florence.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.30" class="ltx_p">**NEW SOLUTION:** Here is the trip plan for visiting the 3 European cities for 14 days:</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.31" class="ltx_p">**Day 1-5:** Arriving in Barcelona and visit Barcelona for 5 days.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.32" class="ltx_p">**Day 6:** Fly from Barcelona to Florence.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.33" class="ltx_p">**Day 6-11:** Visit Florence for 6 days (meeting the friend during this time).</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.34" class="ltx_p">**Day 12:** Fly from Florence to Barcelona.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.35" class="ltx_p">**Day 12-13:** Spend an extra day in Barcelona.</span>
<span id="A5.p2.pic1.2.2.2.2.1.1.36" class="ltx_p">**Day 14:** Fly from Barcelona to Helsinki.</span>
</span></foreignObject></g></g></g></svg>
</div>
<div class="ltx_pagination ltx_role_newpage"></div>
</section>
</article>
</div>
<div class="ar5iv-footer"><a href="/html/2406.04519" class="ar5iv-nav-button ar5iv-nav-button-prev">◄</a>
    <a class="ar5iv-home-button" href="/"><img height="40" alt="ar5iv homepage" src="/assets/ar5iv.png"></a>
    <a href="/feeling_lucky" class="ar5iv-text-button">Feeling<br>lucky?</a>
    <a href="/log/2406.04520" class="ar5iv-text-button ar5iv-severity-warning">Conversion<br>report</a>
    <a class="ar5iv-text-button" target="_blank" href="https://github.com/dginev/ar5iv/issues/new?template=improve-article--arxiv-id-.md&title=Improve+article+2406.04520">Report<br>an issue</a>
    <a href="https://arxiv.org/abs/2406.04520" class="ar5iv-text-button arxiv-ui-theme">View&nbsp;original<br>on&nbsp;arXiv</a><a href="/html/2406.04521" class="ar5iv-nav-button ar5iv-nav-button-next">►</a>
</div><footer class="ltx_page_footer">
<a class="ar5iv-toggle-color-scheme" href="javascript:toggleColorScheme()" title="Toggle ar5iv color scheme"><span class="color-scheme-icon"></span></a>
<a class="ar5iv-footer-button" href="https://arxiv.org/help/license" target="_blank">Copyright</a>
<a class="ar5iv-footer-button" href="https://arxiv.org/help/policies/privacy_policy" target="_blank">Privacy Policy</a>

<div class="ltx_page_logo">Generated  on Fri Jul  5 21:12:39 2024 by <a target="_blank" href="http://dlmf.nist.gov/LaTeXML/" class="ltx_LaTeXML_logo"><span style="letter-spacing:-0.2em; margin-right:0.1em;">L<span class="ltx_font_smallcaps" style="position:relative; bottom:2.2pt;">a</span>T<span class="ltx_font_smallcaps" style="font-size:120%;position:relative; bottom:-0.2ex;">e</span></span><span style="font-size:90%; position:relative; bottom:-0.2ex;">XML</span><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAsAAAAOCAYAAAD5YeaVAAAAAXNSR0IArs4c6QAAAAZiS0dEAP8A/wD/oL2nkwAAAAlwSFlzAAALEwAACxMBAJqcGAAAAAd0SU1FB9wKExQZLWTEaOUAAAAddEVYdENvbW1lbnQAQ3JlYXRlZCB3aXRoIFRoZSBHSU1Q72QlbgAAAdpJREFUKM9tkL+L2nAARz9fPZNCKFapUn8kyI0e4iRHSR1Kb8ng0lJw6FYHFwv2LwhOpcWxTjeUunYqOmqd6hEoRDhtDWdA8ApRYsSUCDHNt5ul13vz4w0vWCgUnnEc975arX6ORqN3VqtVZbfbTQC4uEHANM3jSqXymFI6yWazP2KxWAXAL9zCUa1Wy2tXVxheKA9YNoR8Pt+aTqe4FVVVvz05O6MBhqUIBGk8Hn8HAOVy+T+XLJfLS4ZhTiRJgqIoVBRFIoric47jPnmeB1mW/9rr9ZpSSn3Lsmir1fJZlqWlUonKsvwWwD8ymc/nXwVBeLjf7xEKhdBut9Hr9WgmkyGEkJwsy5eHG5vN5g0AKIoCAEgkEkin0wQAfN9/cXPdheu6P33fBwB4ngcAcByHJpPJl+fn54mD3Gg0NrquXxeLRQAAwzAYj8cwTZPwPH9/sVg8PXweDAauqqr2cDjEer1GJBLBZDJBs9mE4zjwfZ85lAGg2+06hmGgXq+j3+/DsixYlgVN03a9Xu8jgCNCyIegIAgx13Vfd7vdu+FweG8YRkjXdWy329+dTgeSJD3ieZ7RNO0VAXAPwDEAO5VKndi2fWrb9jWl9Esul6PZbDY9Go1OZ7PZ9z/lyuD3OozU2wAAAABJRU5ErkJggg==" alt="Mascot Sammy"></a>
</div></footer>
</div>

    <script>
      var canMathML = typeof(MathMLElement) == "function";
      if (!canMathML) {
        var body = document.querySelector("body");
        body.firstElementChild.setAttribute('style', 'opacity: 0;');
        var loading = document.createElement("div");
        loading.setAttribute("id", "mathjax-loading-spinner");
        var message = document.createElement("div");
        message.setAttribute("id", "mathjax-loading-message");
        message.innerText = "Typesetting Equations...";
        body.prepend(loading);
        body.prepend(message);

        var el = document.createElement("script");
        el.src = "https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js";
        document.querySelector("head").appendChild(el);

        window.MathJax = {
          startup: {
            pageReady: () => {
              return MathJax.startup.defaultPageReady().then(() => {
                body.removeChild(loading);
                body.removeChild(message);
                body.firstElementChild.removeAttribute('style');
              }); } } };
      }
    </script>
    <script>
    // Auxiliary function, building the preview feature when
    // an inline citation is clicked
    function clicked_cite(e) {
      e.preventDefault();
      let cite = this.closest('.ltx_cite');
      let next = cite.nextSibling;
      if (next && next.nodeType == Node.ELEMENT_NODE && next.getAttribute('class') == "ar5iv-bibitem-preview") {
        next.remove();
        return; }
      // Before adding a preview modal,
      // cleanup older previews, in case they're still open
      document.querySelectorAll('span.ar5iv-bibitem-preview').forEach(function(node) {
        node.remove();
      })

      // Create the preview
      preview = document.createElement('span');
      preview.setAttribute('class','ar5iv-bibitem-preview');
      let target = document.getElementById(this.getAttribute('href').slice(1));
      target.childNodes.forEach(function (child) {
        preview.append(child.cloneNode(true));
      });
      let close_x = document.createElement('button');
      close_x.setAttribute("aria-label","Close modal for bibliography item preview");
      close_x.textContent = "×";
      close_x.setAttribute('class', 'ar5iv-button-close-preview');
      close_x.setAttribute('onclick','this.parentNode.remove()');
      preview.append(close_x);
      preview.querySelectorAll('.ltx_tag_bibitem').forEach(function(node) {
        node.remove();
      });
      cite.parentNode.insertBefore(preview, cite.nextSibling);
      return;
    }
    // Global Document initialization:
    // - assign the preview feature to all inline citation links
    document.querySelectorAll(".ltx_cite .ltx_ref").forEach(function (link) {
      link.addEventListener("click", clicked_cite);
    });
    </script>
    </body>
</html>

2406.04520
We introduceNatural Plan, a realistic planning benchmark in natural language containing 3 key tasks:Trip Planning,Meeting Planning, andCalendar Scheduling. We focus our evaluation on the planning capabilities of LLMs with full information on the task, by providing outputs from tools such as Google Flights, Google Maps, and Google Calendar as contexts to the models. This eliminates the need for a tool-use environment for evaluating LLMs on Planning. We observe thatNatural Planis a challenging benchmark for state of the art models. For example, inTrip Planning, GPT-4 and Gemini 1.5 Pro could only achieve 31.1% and 34.8% solve rate respectively. We find that model performance drops drastically as the complexity of the problem increases: all models perform below 5% when there are 10 cities, highlighting a significant gap in planning in natural language for SoTA LLMs. We also conduct extensive ablation studies onNatural Planto further shed light on the (in) effectiveness of approaches such as self-correction, few-shot generalization, and in-context planning with long-contexts on improving LLM planning.
abstract
Natural Plan: Benchmarking LLMs on Natural Language Planning
Abstract
2406.04520
1IntroductionLarge language models (LLMs)  such as Geminiand GPT4have demonstrated great potentials in solving complex tasks, such as understanding natural language, reasoningand code generation. The planning capability of these models however are still far behind human performance. Even though many recent works target to tackle this problem, without realistic benchmarks that reflect real-world applications, it is difficult to make meaningful progress in enhancing these models’ planning abilities.Planninghas been exhaustively studied in robotics and embodied environments. Automated planning algorithms
have been widely usedto enable planning in such systems. In these settings, planning involves coming up with a sequence of actions which when executed would take an agent from a certain initial state to a desired world state. These systems frequently use planning domain description language (PDDL) or answer set programming (ASP) as the underlying action language for the planners. Even though recent works have explored the potential of LLM-powered agents in classical planning settings, planning scenarios are not in practical setting and they are not in natural language as they often contains templates.Figure 1:Illustrative example of theTrip Planningtask.Figure 2:Illustrative example of theMeeting Planningtask.Figure 3:Illustrative example of theCalendar Schedulingtask.In this paper we introduceNatural Plan, a new benchmark specifically designed to assess how well LLMs can handle planning tasks described in natural language.Natural Planincludes three different planning tasks i.e.,Trip Planning,Meeting Planning,Calendar Scheduling. For each task we gather real information from the existing tools. For example, inTrip Planningwe query Google Flights API and provide the flight connectivity information between cities in the context. Figures1-3illustrate the tasks along with associated google tools that provide information as context.Our evaluation shows thatNatural Planis a hard benchmark for state of the art models. For example, in theTrip Planning task, GPT-4 and Gemini 1.5 Pro achieves 31.1% and 34.8% performance, while GPT-3.5 is only at 7.3% and GPT-4o is at 3.7%. We find that model performance reduces significantly as the complexity of the task increases e.g. an increase in number of people, cities or days in the question. Self-correction does not help models in improving performance. We also observe interesting insights in our easy to hard and hard to easy generalization experiments. Lastly, we conduct study of in-context planning with long context, and show that Gemini 1.5 Pro significantly outperforms other models withaccuracy on Trip Planning andon Calendar Scheduling.
introduction
Natural Plan: Benchmarking LLMs on Natural Language Planning
1Introduction
2406.04520
2Natural PlanNatural Planis a benchmark designed to evaluate capability of LLMs in performing planning tasks expressed in natural language. In this section, we discuss about various categories we have inNatural Plan, our dataset construction process, quality measures and some statistics.2.1Dataset CategoriesNatural Planhas 3 planning categories:Trip Planning,Meeting PlanningandCalendar Scheduling. Each of these is intended to capture a real world planning task involving some tools such as Google flights. We decouple tool-use from the reasoning task and provide tool outputs in-context to keep focus ofNatural Planon planning. We believe this will significantly simplify the process of evaluating planning for LLMs.2.1.1Trip PlanningTrip Planningis a task focusing on planning a trip itinerary under given constraints. An example prompt and solution is shown in AppendixA. The task is to find the itinerary regarding the order of visitingcities. We add enough constraints such that there is only one solution to the task, which makes the evaluation of the predictions straightforward.2.1.2Meeting PlanningThis portion of the benchmark focuses on scheduling meetings under various given constraints. Givenfriends, this task provides the meeting times as well as their locations. AppendixAdemonstrates an example question. The objective is to meet as many friends as possible given the constraints, which include travel time between locations.2.1.3Calendar SchedulingCalendar Schedulingis a task focusing on scheduling work meetings between multiple people given existing schedules and various constraints. We vary the number of people involved in the meeting and the number of workdays, in order to vary the task difficulties. AppendixAdemonstrates an example question.2.2Dataset ConstructionWe createNatural Plansynthetically by using corresponding tool data and creating various constraints. We describe below the specific creation process for each category of task.2.2.1Trip PlanningWe create the dataset in the following way: To create a question, we randomly samplecities from the top-48 visited cities in Europe. We also randomly sample the total duration and the number of days spent in each city with. We add constraints to the itinerary requiring visiting some cities during particular days, e.g.meeting a friend in Paris from day 3 to day 5 on the trip. As a global constraint, we add the preference of commuting between cities using direct flights only, excluding the possibility of visiting city Y after X if there is no direct flight from X to Y. To assist the LLM with the connectivity constraint, we query Google Flights API and provide the flight connectivity information between cities in the context.2.2.2Meeting PlanningFor this dataset category, we randomly sample the person names to meet with and corresponding locations. We also sample time frames showing availability of persons. We add constraints in terms of availability of the subject e.g. you are visiting San Francisco for a day. The goal in this set up is to meet as many friends as possible. In order to make the problem realistic, the time constraints / locations follow real world locations. Travel distances are estimated by querying driving times via the Google Maps API.2.2.3Calendar SchedulingThis portion of the dataset includes tasks to schedule a meeting of either 30 minutes or an hour among various number of attendees in one or multiple of the work days.
We instantiated two subsets: the first set fixes the meeting on a specific day, e.g., Monday while varying the number of attendees in; the second set fixes the number of attendees to 2 while varying the number of work days the meeting can be scheduled over in. Each person involved in the meeting comes with their existing meeting schedule during the day (first set)  or the week (second set) , which was created by adding random meetings of 30 minutes to the days untilhours of meeting time is filled. We randomly assignto each attendee to make sure half of the attendees have busy schedule, meaning more than half of their working hours are spent in meetings, while the other half have light schedule with less than half of the working hours spent in meetings. Consecutive meetings of each attendee are combined into a single block as shown in Figure3. Once we have the existing schedules of all attendees, we add two types of constraints: 1)  earliest availability; 2)  avoid meeting during certain time frame to make sure there is a single solution to the problem.2.3StatisticsTable1shows statistics of various tasks acrossTrip Planning,Meeting Planning, andCalendar SchedulinginNatural Plan.Table 1:Statistics ofNatural Plantasks.Task#Test ExamplesTrip Planning1600Meeting Planning1000Calendar Scheduling1000
body
Natural Plan: Benchmarking LLMs on Natural Language Planning
2Natural Plan
2406.04520
3ExperimentWe conduct various experiments to evaluate state-of-the-art LLMs on the planning tasks inNatural Plan.3.1ModelsWe experiment several state-of-the-art LLMs: GPT-4 (gpt-4-turbo-2024-04-09) , GPT-3.5 (gpt-3.5-turbo-0125) , GPT-4o (gpt-4o-2024-05-13) , and Gemini 1.5 Flash and Pro.3.2SetupsFew-ShotFor each task inNatural Plan, we present 5 examples within the same task as few-shot exemplars to enable the LLM in-context learningfrom the examples (see AppendixBfor the few-shot prompt) . This setup also ensures that outputs can be easily parsed for scoring.Constraint Complexity UnderstandingTo gain a better understanding of the planning ability of LLMs, we vary the difficulty level of each task through a controlled variable.
We conduct analysis by varying constraints such as number of people, number of cities, number of days etc. to better understand behavior of models across the variation in the complexity of the planning task.Few-Shot GeneralizationWe conduct easy-to-hard and hard-to-easy generalization study by providing easier and harder examples as in-context exemplars, respectively. For instance, for easy-to-hard (hard-to-easy)  generalization inTrip Planning, we provide 5 easier (harder)  examples with 2 fewer (more)  cities than the ones in the evaluation task instances.Self-CorrectionWe evaluate if models can self-correct their mistakes across various categories of tasks inNatural Plan. Here we prompt the model to identify if there are any mistakes and self correct if necessary.In-Context Planning with Long ContextWe evaluate how well models can leverage the long-context capabilities for in-context learning in planning. We split the test-set into 80% and 20%, where 80% is used as in-context examples while we evaluate the model performance on 20% of the test-set. We increase the number of few-shot examples used up to 800.EvaluationWe parse the output from the LLM, and compare it with the golden plan. We compute an exact match (EM)  score of the LLM-generated plan being identical to the golden plan. See AppendixCfor the details of parsing and scoring.
body
Natural Plan: Benchmarking LLMs on Natural Language Planning
3Experiment
2406.04520
4Results and AnalysisTable 2:Accuracy of 5 models onNatural Plan.TaskGPT-3.5GPT-4GPT-4oGemini 1.5 FlashGemini 1.5 ProTrip Planning7.3%31.1%3.7%25.6%34.8%Meeting Planning19.1%47.0%45.2%23.9%39.1%Calendar Scheduling19.9%41.2%43.7%34.3%48.9%4.1ResultsTable2shows the performance of various LLMs across tasks inNatural Planin the 5-shot setup. We get the following insights from the results.All models perform poorly onNatural Plan.Gemini 1.5 Pro performs the best onTrip PlanningandCalendar Schedulingwhile GPT-4 does the best onMeeting Planning.InTrip Planning, Gemini 1.5 Pro achieves 34.8% accuracy while GPT-4 is 31.1%. In particular, we observe that GPT-4o is only at 3.7%. Further analysis shows that GPT-4o is struggling to understand and respect the flight connectivity and travel date constraints, see AppendixDfor a more detailed analysis.
GPT-4 and GPT-4o achieve 47% and 45.2% accuracy onMeeting Planningwhile Gemini 1.5 Pro is 39.1%. ForCalendar Scheduling, Gemini 1.5 Pro outperforms GPT-4 and GPT-4o at 48.9%.Comparing the three tasks inNatural Plan,Trip Planningis the hardest among them with the lowest best accuracy of 34.8%. Note all models have accuracy below 50% on all three tasks inNatural Plan, highlighting that planning in natural language is still a very challenging task even for the state of the art models, despite that all tool-use information needed is provided in the context.4.2Constraint ComplexityFigures4-6show the performance variation of models across variation in number of cities inTrip Planning, number of people inMeeting Scheduling, and number of attendees/days inCalendar Scheduling. We observe the following key insights:Figure 4:Constraint complexity analysis of theTrip Planningtask inNatural Planas a function of number of cities.Figure 5:Constraint complexity analysis of theMeeting Planningtask inNatural Planas a function of number of people.Figure 6:Constraint complexity analysis of theCalendar Schedulingtask as a function of the number of people involved to meet during a single day (left) , and number of working days to choose a meeting time from between two attendees (right) .Model performance reduces significantly as the task complexity increases as number of cities/number of people/number of attendees/number of days increase.ForTrip Planning, Figure4shows that models start to fail with more cities involved in the planning. InTrip Planning, all five models perform below 5% when there are 10 cities. ForMeeting Planning, we evaluate scenarios with the number of people to meet from 1 to 10. Figure5again shows that the performance drops sharply with more people to meet. Beyond 8 people, all models have a score lower than 10%. ForCalendar Scheduling, the drop of accuracy is not as significant when increasing number of attendees or number of days compared to the other two tasks.4.3Generalization AnalysisFigure 7:Model performance on theTrip Planningtask as a function of number of cities for few-shot generalization ablations: E2H=easy-to-hard, H2E=hard-to-easy.Figure7shows the summary of our easy-to-hard and hard-to-easy generalization experiments. For easy-to-hard (hard-to-easy)  generalization, we present 5 easier (harder)  examples with 2 fewer (more)  cities than the task, to test whether LLMs can generalize from easier (harder)  in-context learning examples. We chooseTrip Planningto conduct our ablations on given that it is the most difficult task amongNatural Plantasks.In general, we observe that easy-to-hard performs better than hard-to-easy generalization across model families.Section4.2shows models perform worse when the task complexity is higher. This result indicates that understanding and making use of hard demonstrations in in-context learning is still challenging even for state of the art LLMs. However, we do observe that for GPT-4 and Gemini 1.5 Flash, the trend is reversed as the task complexity increases: for, hard-to-easy demonstrations work better than easy-to-hard.4.4Self-CorrectionFigure 8:Accuracy ofTrip Planningas a function of number of cities for self-correction ablations. SC=self-correctionFigure8shows the results of performing self-correction on model predictions in theTrip Planningtask. We prompt the LLM to check whether the generated plan is correct or not, and if determined incorrect, fix the plan (see AppendixBfor the prompt) .Self-correction leads to significant model performance drop across all models. Interestingly, the stronger models such as GPT-4 and Gemini 1.5 Pro suffer bigger loss compared to GPT-3.5.This aligns well with previous findings that self-correction could lead to performance degradation on Reasoning. The stronger instruction-tuned models like GPT-4 and Gemini 1.5 Pro could be over-confident towards correcting its own solutions when prompted, see AppendixEfor examples of self-correction.4.5In-Context Planning with Long ContextFigure 9:In-Context planning with long context forTrip PlanningandCalendar Schedulingtasks. Gemini 1.5 Pro shows strong long-context learning on Planning compared to other models.In this section, we study the possibility of in-context planning by leveraging the long context capabilities of recent models. Figure9shows the performance of four models up to 800 shots.Due to the strong long context capabilities, Gemini Pro 1.5 is able to leverage more in-context examples up to 355K tokens, still showing steady improvements.For instance, inTrip Planning, increasing number of shots from 1 to 800 brings up the accuracy of Gemini Pro 1.5 from 2.7% to 39.9%. In the mean time, both GPT-4 and Gemini 1.5 Flash peak at 20-shot and start to show performance degradation. The same is observed inCalendar Schedulingwhere Gemini 1.5 Pro continually improves up to 400 shots. These results show the promise of in-context planning where the long-context capabilities enable LLMs to leverage further context to improve Planning.
body
Natural Plan: Benchmarking LLMs on Natural Language Planning
4Results and Analysis
2406.04520
5Related WorksPlanning empowers intelligent agents to look ahead and proactively determine a course of action to reach objectives. Automated/classical planning is a subarea of AI that allows sequential decision-making systems to choose a sequence of actions using which they complete a (set of)  task(s)  autonomously. Most of the planning formalisms use a Planning Domain Definition Language (PDDL) , where it separates the environment dynamics (domain definition)  from the environment configuration (problem definition) . Domain-independent planners like Fast-Forward, Fast-Downward, etc. take these domain and problem definitions as input and generate a sequence of actions that takes a planning agent from a given initial state to a state satisfying a goal condition (also given as input with the problem definition) . Such classical planning methods
have been widely adopted in robots and embodied environments.
Most planning benchmarks111https://www.icaps-conference.org/competitions/use similar formulations with variations like probabilities, numeric fluents222https://ipc2023-numeric.github.io/, temporal actions, etc. as benchmarks. The main issue with such benchmarks is that they are not expressed in natural language and hence need experts to handcraft the domains and problems.Recently prompting LLMs to extract common sense knowledge gained attention. Effectiveness of LLMs in generating plans has been studied by. Whiletranslate natural language instructions into the executable programming languages, such as PDDL, and runs classical planning algorithms,uses the LLM as both a world model and a reasoning agent, enhanced by a Monte Carlo Tree Search algorithm for efficient exploration.Even though these works target to improve the planning capability of LLMs, these are not able to perform well in more complex and realistic settings, closer to those in which humans operate. TravelPlannerprovides a sandbox with various tools to evaluate language model capabilities in performing planning via agents. Our workNatural Planprovides a holistic benchmark in natural language to evaluate the planning capability of models in real world tasks.
body
Natural Plan: Benchmarking LLMs on Natural Language Planning
5Related Works
2406.04520
6ConclusionWe introduceNatural Planto evaluate the capability of LLMs to plan on real world tasks given in natural language.Natural Plancovers three domains:Trip Planning,Calendar Scheduling, andMeeting Planning. The tasks also contain API results from various tools such as Google Calendar, Google Flights and Google Maps mimicking real world planning tasks with tools. We find thatNatural Planis very hard for state of the art models to solve. Models increasingly struggle as the complexity of the problem increases, e.g. an increase in number of people, cities or days in the question. However, our in-context planning experiments demonstrate the potential promise of leveraging the long-context capabilities to boost LLMs’ planning ability.AcknowledgmentsWe acknowledge careful review and feedback from Uri Alon and Aleksandra Faust of Google DeepMind on the draft of this paper.
conclusion
Natural Plan: Benchmarking LLMs on Natural Language Planning
6Conclusion