PaperlayerView exact revision on arXiv

Source-linked AI summary

NATURAL PLAN: Benchmarking LLMs on Natural Language Planning

Huaixiu Steven Zheng, Swaroop Mishra, Hugh Zhang, Xinyun Chen, Minmin Chen, Azade Nova, Le Hou, Heng-Tze Cheng, Quoc V. Le, Ed H. Chi, Denny Zhou

arXiv:2406.04520v1cs.CLcs.AI

TL;DR

NATURAL PLAN addresses the need for realistic natural-language planning benchmarks by supplying tool outputs as context across three planning tasks. Models struggle across the tasks, especially as complexity increases, while long-context in-context planning shows promise.

  • Problem

    LLM planning remains behind human performance, and the absence of realistic benchmarks makes meaningful progress difficult to assess.

    Source: §1 · p. 1

  • Method

    NATURAL PLAN benchmarks Trip Planning, Meeting Planning, and Calendar Scheduling in natural language, providing real tool outputs such as Google Flights and Google Maps information as context.

    Source: §1 · p. 2, §6 · p. 9

  • Results

    Below 50% accuracy across all three tasks, all models struggle; Trip Planning is hardest, with a best accuracy of 34.8%.

    Source: §4.1 · p. 5

  • Takeaways & Limitations

    Models increasingly struggle as problem complexity rises, while long-context in-context planning experiments show potential to boost planning ability.

    Source: §6 · p. 9

Abstract

from arXiv · show

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 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 NATURAL PLAN is a challenging benchmark for state of the art models. For example, in Trip 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 on NATURAL PLAN 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.

1 Introduction

The paper motivates a realistic benchmark for natural-language planning, where LLM planning remains behind human performance. NATURAL PLAN provides real tool outputs as context across three planning tasks and finds that state-of-the-art models struggle, especially as task complexity increases.

1 Introduction

  • The authors argue that realistic benchmarks are needed to make meaningful progress on LLM planning, which remains behind human performance.Prior planning work often uses templated scenarios rather than practical settings expressed in natural language.Source: §1 · p. 1
  • NATURAL PLAN evaluates natural-language planning in Trip Planning, Meeting Planning, and Calendar Scheduling using real information from existing tools as model context.For Trip Planning, the context includes flight connectivity queried from the Google Flights API.Source: §1 · p. 2
  • In Trip Planning, Gemini 1.5 Pro reaches 34.8% performance and GPT-4 31.1%, while GPT-3.5 reaches 7.3% and GPT-4o 3.7%.Performance falls as task complexity increases; self-correction does not improve it, and long-context planning reaches approximately 40% accuracy on Trip Planning and 50% on Calendar Scheduling for Gemini 1.5 Pro.Source: §1 · p. 2

2 NATURAL PLAN

NATURAL PLAN is a synthetic benchmark for evaluating LLM planning in natural language, with three task categories and tool-derived information supplied as context. Its construction varies task constraints and difficulty across trip, meeting, and calendar planning.

2 NATURAL PLAN

  • NATURAL PLAN evaluates LLMs on natural-language planning while providing tool outputs in context to separate planning from tool use.Its three categories are Trip Planning, Meeting Planning, and Calendar Scheduling.Source: §2.1 · p. 3, §2 · p. 3

2.1.1 Trip Planning

  • Trip Planning asks for an itinerary visiting N cities under constraints, with enough constraints added to ensure a single solution.The dataset samples 3–10 European cities, trip durations of 2–7 days, day-specific requirements, and direct-flight constraints; Google Flights connectivity is provided in context.Source: §2.1.1 · p. 3, §2.2.1 · p. 3

2.1.2 Meeting Planning

  • Meeting Planning asks participants to meet as many friends as possible, subject to availability, the planner’s constraints, locations, and travel time.The dataset uses real-world locations and estimates driving times through the Google Maps API.Source: §2.1.2 · p. 3, §2.2.2 · p. 3

2.1.3 Calendar Scheduling

  • Calendar Scheduling involves scheduling work meetings among multiple people with existing schedules and other constraints.The dataset varies attendee and workday counts; it includes 30-minute or hour-long meetings, busy and light schedules, earliest-availability constraints, and time frames to avoid.Source: §2.1.3 · p. 3, §2.2.3 · p. 4

2.2 Dataset Construction

  • The benchmark is created synthetically from corresponding tool data and task-specific constraints.The supplied passages describe construction for Trip Planning and Meeting Planning, and detailed schedule generation for Calendar Scheduling.Source: §2.2 · p. 3, §2.2.1 · p. 3, §2.2.2 · p. 3

2.2.1 Trip Planning

  • Trip Planning instances sample cities, trip lengths, city stays, day-specific requirements, and direct-flight constraints.Flight connectivity information from Google Flights is supplied to help with the connectivity constraint.Source: §2.2.1 · p. 3

2.2.2 Meeting Planning

  • Meeting Planning instances sample people, locations, availability windows, and planner constraints, with driving times estimated from Google Maps.The objective is to meet as many friends as possible.Source: §2.2.2 · p. 3

2.2.3 Calendar Scheduling

  • Calendar Scheduling instances vary meeting duration, attendee count, and the number of workdays, and construct existing schedules with availability constraints.The passage describes constraints intended to ensure a single solution.Source: §2.2.3 · p. 4

3 Experiment

The experiments evaluate state-of-the-art LLMs on NATURAL PLAN with few-shot prompting and controlled variations in task complexity. They also test generalization, self-correction, long-context in-context planning, and exact-match scoring.

3.1 Models

  • The experiments evaluate GPT-4, GPT-3.5, GPT-4o, and Gemini 1.5 Flash and Pro on NATURAL PLAN.The cited passage specifies the model versions used for GPT-4, GPT-3.5, and GPT-4o.Source: §3.1 · p. 4

3.2 Setups

  • Few-shot evaluation provides five same-task examples as in-context exemplars, with outputs formatted for parsing and scoring.The setup is intended to support in-context learning from examples.Source: §3.2 · p. 4
  • Constraint-complexity analysis varies factors such as the number of people, cities, or days to examine model behavior across task difficulty levels..Source: §3.2 · p. 4
  • Few-shot generalization tests easy-to-hard and hard-to-easy transfer using examples with different difficulty from the evaluation instances.For Trip Planning, the setup uses five examples with two fewer or two more cities, respectively.Source: §3.2 · pp. 4–5
  • The self-correction setup prompts models to identify mistakes and correct them when necessary.The evaluation covers various categories of NATURAL PLAN tasks.Source: §3.2 · p. 5
  • Long-context in-context planning uses 80% of the test set as examples, evaluates on the remaining 20%, and increases the number of examples up to 800.The setup tests whether models can leverage long-context capabilities for planning.Source: §3.2 · p. 5
  • Evaluation parses each model output and scores whether its plan exactly matches the gold plan.The metric is exact match (EM).Source: §3.2 · p. 5

4 Results and Analysis

Results across NATURAL PLAN show low accuracy and marked sensitivity to task complexity. Ablations report differing effects from demonstration difficulty, self-correction, and long-context examples.

4.1 Results

  • All model accuracies stay below 50%; Gemini 1.5 Pro leads Trip Planning (34.8%) and Calendar Scheduling (48.9%), while GPT-4 leads Meeting Planning (47%), and Trip Planning is hardest.Trip Planning has the lowest best accuracy among the three tasks.Source: Table 2 · p. 5, §4.1 · p. 5

4.2 Constraint Complexity

4.3 Generalization Analysis

  • Easy-to-hard generalization generally outperforms hard-to-easy, but GPT-4 and Gemini 1.5 Flash reverse that trend for N = 5 ∼8.The ablations use Trip Planning, the benchmark’s hardest task, with five easier or harder examples than the evaluated task.Source: §4.3 · p. 7, Figure 7 · p. 7

4.4 Self-Correction

  • Self-correction significantly reduces performance across models, with larger losses for GPT-4 and Gemini 1.5 Pro than for GPT-3.5.The authors suggest stronger instruction-tuned models may be overconfident when correcting their own solutions.Source: §4.4 · p. 8, Figure 8 · p. 8

4.5 In-Context Planning with Long Context

  • With up to 355K-token contexts, Gemini 1.5 Pro improves Trip Planning from 2.7% at 1 shot to 39.9% at 800 shots; GPT-4 and Gemini 1.5 Flash peak at 20 shots, then degrade.Gemini 1.5 Pro’s Calendar Scheduling performance continues improving up to 400 shots.Source: Figure 9 · p. 8, §4.5 · pp. 8–9

5 Related Works

Classical planning benchmarks use formal representations that require expert-authored domains and problems, while LLM planning work has explored both classical-planner pipelines and LLM-based reasoning. NATURAL PLAN is positioned as a holistic natural-language benchmark for real-world planning tasks.

  • Classical planning benchmarks commonly use formal formulations such as PDDL, requiring experts to handcraft domains and problems.Source: §5 · p. 9
  • Prior LLM approaches translate instructions into executable languages and run classical planners, or use an LLM as world model and reasoning agent with Monte Carlo Tree Search [Valmeekam et al., 2024, Guan et al., 2024; Hao et al., 2023].Source: §5 · p. 9
  • Earlier approaches have not performed well in more complex, realistic settings [Valmeekam et al., 2022]; TravelPlanner uses a tool sandbox, whereas NATURAL PLAN provides a holistic natural-language benchmark [Xie et al., 2024].Source: §5 · p. 9

6 Conclusion

NATURAL PLAN evaluates LLM planning across three real-world task domains using tool outputs as context. Models struggle as problem complexity increases, while in-context planning experiments show potential for long-context capabilities to improve planning.

  • NATURAL PLAN covers Trip Planning, Calendar Scheduling, and Meeting Planning, with API results from tools such as Google Calendar, Google Flights, and Google Maps in context.Source: §6 · p. 9
  • State-of-the-art models find the benchmark difficult, and performance declines as the number of people, cities, or days increases.Source: §6 · p. 9
  • In-context planning experiments show potential for leveraging long-context capabilities to boost LLM planning ability.Source: §6 · p. 9

A NATURAL PLAN Examples

The appendix illustrates the benchmark with example prompts and solutions for trip, meeting, and calendar planning, then provides templates for few-shot and ablation prompts.

A NATURAL PLAN Examples

Trip Planning

  • The trip example combines a 14-day, three-city itinerary, stay durations, direct-flight connections, and a requirement to meet a friend in Florence between days 9 and 14.Its solution orders visits through Helsinki, Barcelona, and Florence, with flights on days 5 and 9.Source: Trip Planning · p. 12

Meeting Planning

  • The meeting example gives participant availability, minimum meeting lengths, and travel-time information; its proposed schedule meets John and Joseph with travel and waiting time between meetings.Source: Meeting Planning · p. 12

Calendar Scheduling

  • The calendar example asks for a 30-minute Monday meeting during work hours and provides Harold’s and Patrick’s availability; the proposed time is 9:30–10:00.Source: Calendar Scheduling · p. 13

B Prompts

  • The appendix provides a five-shot Trip Planning prompt with example tasks and solutions, and says similar prompts are used for the other two tasks.Source: B Prompts · p. 13
  • The easy-to-hard and hard-to-easy Trip Planning ablation prompt uses example tasks labeled by difficulty.Source: B Prompts · pp. 13–14
  • A separate Trip Planning prompt asks the model to identify errors in a proposed solution, correct them, and return the revised solution in a specified format.Source: B Prompts · p. 14

C Plan Parsing and Scoring

Plans are evaluated by parsing generated outputs into task-specific information and comparing that information against ground-truth plans using exact match.

  • Few-shot exemplars encourage a consistent solution template, after which regex expressions extract dates, places, and times from generated plans.For Trip Planning, the parser extracts the flight date and origin and destination cities.Source: C Plan Parsing and Scoring · p. 14
  • A plan is correct only when all extracted information matches the ground-truth plan.Source: C Plan Parsing and Scoring · p. 14

D Analysis of GPT-4o on Trip Planning

In a sample of GPT-4o’s Trip Planning errors, every error involved failing to respect task constraints. The examples illustrate failures involving travel dates and flight connectivity.

D Analysis of GPT-4o on Trip Planning

  • 7/10 sampled errors violated flight-connectivity constraints, while the remaining 3/10 violated travel-date constraints.The analysis sampled 10 GPT-4o Trip Planning errors.Source: D Analysis of GPT-4o on Trip Planning · p. 14
  • The 14-day task’s supplied direct-flight connections support the Helsinki–Barcelona–Florence route shown in the solution.The stated connections are Helsinki–Barcelona and Barcelona–Florence; the solution schedules those legs and places the Florence visit on days 9–14.Source: D Analysis of GPT-4o on Trip Planning · p. 15
  • In the 8-day Berlin, Munich, and Dubrovnik task, GPT-4o’s proposed itinerary runs through day 10 instead of fitting the requested duration.The task specifies Berlin for 4 days, Munich for 3, and Dubrovnik for 3; the output schedules those stays across days 1–4, 4–7, and 7–10.Source: D Analysis of GPT-4o on Trip Planning · p. 16

E Self-Correction Example

The self-correction example marks the model’s errors in red.

E Self-Correction Example

  • Errors made by the models are highlighted in red in the self-correction example.The passage introduces the example as illustrating model behavior after self-correction.Source: E Self-Correction Example · p. 16

Self-Correction Example

The example presents a 14-day, three-city trip-planning task and model responses that identify or retain constraint errors. The proposed new solutions also differ in how they schedule the visit and flights.

Self-Correction Example

  • The task requires a 14-day visit to Florence, Barcelona, and Helsinki, with a friend visit in Florence between days 9 and 14 and only direct flights.The supplied connections are Barcelona–Florence and Helsinki–Barcelona; the example solution routes Helsinki to Barcelona to Florence and schedules Florence for days 9–14.Source: Self-Correction Example · p. 17
  • GPT-3.5 flags a friend-visit date error but proposes a 15-day itinerary, while GPT-4 identifies a 15-day overrun and proposes a different schedule.GPT-3.5’s new solution schedules the trip through day 15; GPT-4’s revised schedule allocates 4 days in Helsinki, 5 in Barcelona, and 5 in Florence.Source: Self-Correction Example · p. 17
  • Gemini Pro 1.5 identifies overlapping use of day 5 and the lack of a direct Helsinki–Florence flight in the proposed solution.The response cites day 5 as both a Helsinki visit day and the flight day to Barcelona.Source: Self-Correction Example · p. 17
  • The new solution schedules Barcelona first, then Florence, then returns to Barcelona before flying to Helsinki.It places the Florence visit on days 6–11, with an extra Barcelona day before the final flight.Source: Self-Correction Example · p. 17
Loading 2406.04520v1…